radix sort in D

radix-sort.d

T[] radixsort(T)(T[] arr, T[] tmparr) {
  assert(arr.length == tmparr.length);

  int[256][T.sizeof] counts;

  foreach (v; arr) {
    foreach (b; 0 .. T.sizeof) {
      uint c = (v >> (b * 8)) & 0xff;
      counts[b][c] += 1;
    }
  }

  loop: foreach (b; 0 .. T.sizeof) {

    int zeroCounts = 0;
    foreach (c; counts[b]) {
      if (c == 0) zeroCounts++;
    }
    if (zeroCounts == 255) continue loop;

    int[256] offsets;

    foreach (i; 1..256) {
      offsets[i] = counts[b][i-1] + offsets[i-1];
    }

    foreach(v; arr) {
      uint c = (v >> (b * 8)) & 0xff;
      tmparr.ptr[offsets[c]] = v;
      offsets[c] += 1;
    }

    auto tmp = arr;
    arr = tmparr;
    tmparr = tmp;
  }

  return arr;
}


void main() {

  import std.datetime;
  import std.conv;
  import std.random;
  import std.range;
  import std.stdio;
  import std.algorithm.sorting;
  import std.algorithm.iteration;

  alias T = uint;
  int len = 16*1024*1024;
  auto rnd = Random(47);
  T[] src = array(rnd.take(len).map!(a => to!T(((to!ulong(a)<<32)+a) & (T.max)) ));

  T[] arr = new T[len];
  T[] tmp = new T[len];

  foreach (iter; 0..4) {
    arr[] = src[];

    StopWatch sw;
    sw.start();
    auto sorted = radixsort(arr, tmp);
    sw.stop();

    writeln(isSorted(sorted));
    writeln(sw.peek().usecs / 1000.0, " ms");
    writeln("* ", sw.peek().hnsecs * 1.0 * 100 / len, " ns/el");
  }
}