Re: Adding my sorting algorithm, ska_sort to boost

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2019-10-15 17:05:04

Hi Malte,

I see there hasn't been much response to your post yet.

Malte Skarupke wrote:
> 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.

> Before I go any further I wanted to ask though:
>
> Does boost want my sorting algorithm? This would essentially deprecate 
> spreadsort since this one is faster and more general and easier to use.

> I think this new version would be great in boost. It's not every day 
> that a new sorting algorithm comes along that's literally twice as 
> fast as what we had before. If we want this in boost, what would the 
> next steps be?

The obvious "next step" would be to see if it can be added to the existing
Boost.Sort library.  Doing that bypasses the public review process.  But
the author of that library may have other ideas.

Personally, often what I need to sort is small or has some complex
comparison function, making radix sort inappropriate.  If I did have
a large dataset, where the performance benefit would be useful, my
first thought would be to find a parallel sort (std:: parallel execution
policy is starting to appear in a few places now.)  Despite that, I
think that what you've got is worthwhile.

Others may be interested in your old blog posts:
https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/

Cheers, Phil.