Another algo for faster sorting

[tsbockman via Digitalmars-d]

On Thursday, 7 April 2016 at 13:32:43 UTC, Andrea Fontana wrote:
> Anyway my topic about sort optimization seems not to have a 
> good luck if not for benchmark inaccuracy :)

I was planning to respond to your original question, I just 
didn't have time last night...

I don't think that the simple "counting sort" you demonstrated in 
the other thread is particularly useful to have in Phobos, by 
itself:
     - It doesn't scale well at all to higher-entropy element 
types, like `int` or `string`.
     - It only works on value types, not reference types.
     - It's so trivial to implement, that anyone who really needs 
it can write it themselves.

However, what might be really useful is to have a good generic 
implementation of "bucket sort". Using a user-supplied fast hash 
function whose output follows the same ordering as the original 
elements:
     1. Move/copy each element into a bucket list chosen by the 
hash function.
     2. Sort each individual bucket list using another algorithm.
     3. Iterate through all the buckets lists, and move/copy each 
element to the output.

With good design, it should be possible to express counting sort 
for small value types like `bool` and `byte` simply as a 
parameterization of bucket sort. (This would require that the 
bucket list type be parameterized, in addition to the hash 
function.)