Re: Adding my sorting algorithm, ska_sort to boost

From: Kostas Savvidis (kotika98_at_[hidden])
Date: 2019-10-15 21:04:29

> 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>