Re: 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.