New fast sorting algorithm (O(n))

[ketmar via Digitalmars-d]

just to show a usecase, some code, ripped out from one of my 
simple engines (sorry for the mess):

import std.stdio;

enum ObjectCount = 1000;


struct RadixSorter(OT)
if (is(OT == class) && is(typeof(OT.init.sortkey) == uint) && 
is(typeof(OT.init.next) : OT))
{
private:
   OT[256] heads;
   OT[256] tails; // hi, Sonic!

private:
   OT rsort(ubyte shift) (OT head) nothrow @trusted @nogc {
     heads[] = null;
     tails[] = null;
     while (head !is null) {
       immutable ubyte bucket = cast(ubyte)(head.sortkey>>shift);
       if (heads.ptr[bucket] is null) {
         heads.ptr[bucket] = tails.ptr[bucket] = head;
       } else {
         tails.ptr[bucket].next = head;
         tails.ptr[bucket] = head;
       }
       auto next = head.next;
       head.next = null;
       head = next;
     }
     OT res, cur;
     foreach (OT o; heads[]) {
       if (o !is null && res is null) { res = cur = o; o = o.next; 
}
       while (o !is null) {
         cur.next = o;
         cur = o;
         o = o.next;
       }
     }
     assert(cur !is null);
     cur.next = null;
     return res;
   }

public:
   void sort (OT[] arr) nothrow @trusted @nogc {
     OT first, cur;
     foreach (OT o; arr) {
       if (first is null) {
         first = cur = o;
       } else {
         cur.next = o;
         cur = o;
       }
     }
     if (first is null) return;
     cur.next = null;
     first = rsort!0(first);
     first = rsort!8(first);
     first = rsort!16(first);
     first = rsort!24(first);
     size_t idx = 0;
     while (first !is null) {
       arr.ptr[idx++] = first;
       first = first.next;
     }
   }
}


class Entity {
   uint sortkey;
   Entity next;
   uint data;

   this () {
     import std.random : uniform;
     sortkey = uniform!"[]"(0, uint.max);
     data = uniform!"[]"(0, uint.max);
   }
}

import std.datetime;

Entity[] objarr;
Entity[] origarr;
Entity[] srtarr;

void genObjects () {
   objarr.length = ObjectCount;
   foreach (ref o; objarr) o = new Entity();
   origarr.length = objarr.length;
   origarr[] = objarr[];
}


void xtest () {
   // radix
   objarr[] = origarr[];
   RadixSorter!Entity rs;
   rs.sort(objarr);
   srtarr.length = objarr.length;
   srtarr[] = objarr[];
   // standard
   objarr[] = origarr[];
   import std.algorithm : sort;
   objarr.sort!((Entity a, Entity b) => a.sortkey < b.sortkey);
   // check if our two sorts are identical
   foreach (immutable idx; 0..objarr.length) {
     if (objarr[idx] !is srtarr[idx]) assert(0, "wtf?!");
   }
}


void check () {
   foreach (immutable idx, const o; objarr) {
     if (idx != 0) {
       if (objarr.ptr[idx-1].sortkey > o.sortkey) assert(0, 
"wtf!?");
     }
   }
}

void testr () {
   objarr[] = origarr[];
   RadixSorter!Entity rs;
   rs.sort(objarr);
   check();
}


void testq () {
   objarr[] = origarr[];
   import std.algorithm : sort;
   objarr.sort!((Entity a, Entity b) => a.sortkey < b.sortkey);
   check();
}


void main () {
   import std.conv : to;
   genObjects();

   xtest();

   auto res = benchmark!(testr, testq)(10000);
   foreach (immutable idx; 0..res.length) {
     writeln(idx, ": ", res[idx].to!Duration.total!"msecs");
   }
}


radix sort is ~8 times faster for 1000 objects here, and ~3 times 
faster for 10000 objects. of course, this can be optimized 
further by removing some clears and so on.