Re: Adding my sorting algorithm, ska_sort to boost

From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2019-10-20 11:24:06

Hi Malte,
I am Francisco Tapia, one of the co-authors of the Sort library.
We will examine your algorithm. But we must examine the internal parts of
the algorithm, and evaluate the correctness of the algorithm, how is
implemented the worst case and a couple of details. After, we check the
speed with the benchmarks used in the library, with several sets of data.
Since the near sorted to the fully unsorted, and from the single numbers to
structs with heavy comparison functions.

Now, I am overburdened by work, and I can't revise until December. But we
will do and provide to you a reasoned response, and according to it, decide
the inclusion or not in the library.
As commented by Phil Endecott, the most interesting now is the parallel
algorithms. Today, we don't have any parallel algorithm based on radix sort
or any other hybrid algorithm.
Because with small sets of data the differences are insignificant. But when
you have big sets of data, use parallel algorithms, and then, the new
single thread algorithms are in the middle, in the no man's land.

If you have any doubt or question, contact me, and I will try to answer you.

El mar., 15 oct. 2019 a las 23:06, Kostas Savvidis via Boost (<
boost_at_[hidden]>) escribió:

>
> > On Oct 13, 2019, at 03:06, Malte Skarupke via Boost <
> boost_at_[hidden]> wrote:
> >
> > Hi,
> > a couple of years ago I wrote a generalized version of radix sort,
> called ska_sort. I gave a talk about it at CppNow, available here:
> > https://www.youtube.com/watch?v=zqs87a_7zxw
> >
> > I have a new version of that algorithm that is both faster and more
> general. I can now sort almost anything. For example when I gave the talk I
> couldn't sort a std::vector<std::list<int>> because std::list doesn't have
> a random access interface, but now that works. (and it's faster than
> sorting the same thing with std::sort)
> >
>
> This seems like a product of a large investment of effort.
> The big advantage over any previously available radix_sort
> is the ability to sort almost any datatype if a key maps to an integer
> somehow.
> Plus, an advantage in measured practical speed, and apparently no claims
> about Big O improvement.
>
> The average performance is O(n*b) where b is unknown and/or dependent on n
> ?
>
> Is  the theoretical worst-case O(n^2) ? Why? Is it because of working
> in-place?
> (yes, I understand you fall back to std::sort if you hit this case)
>
> Is this software/algorithm fully documented? - I mean by another way than
> reading the source code.
>
> Maybe too many questions at once, but it was not clear after watching your
> talk at cppcon and the blog posts.
>
> Cheers,
> Kostas
>
>  <https://www.youtube.com/watch?v=Nz1KZXbghj8>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>