(Improved) Benchmark for Phobos Sort Algorithm

[Craig Black]

It was brought to my attention that the quick sort has a very bad worst 
case, so I implemented a simple fix for it.  Now the worst case (completely 
ordered) is the best case, and it only slows down the general case by a 
small percentage.  I thought to myself, "it can't be this easy to fix quick 
sort".  Does anyone see a flaw in this simple fix?  Performs much better 
than Phobos in completely random and completely sorted data.  Perhaps there 
is another case where it doesn't do as well?

-Craig

import std.stdio;
import std.random;
import std.algorithm;

static bool less(T)(T a, T b) { return a < b; }

bool isOrdered(A, alias L)(A a, int low, int high)
{
  for(int i = low; i < high; i++)
  {
    if(L(a[i+1], a[i])) return false;
  }
  return true;
}

void insertionSort(A, alias L)(A a, int low, int high)
{
  for(int i = low; i <= high; i++)
  {
    int min = i;
    for(int j = i + 1; j <= high; j++)
      if(L(a[j], a[min])) min = j;
    swap(a[i], a[min]);
  }
}

void quickSort(A, alias L)(A a, int p, int r)
{
  if (p >= r) return;
  if(isOrdered!(A, L)(a, p, r)) return;
  if(p + 7 > r) return insertionSort!(A, L)(a, p, r);
  auto x = a[r];
      int j = p - 1;
      for (int i = p; i < r; i++)
      {
            if (L(x, a[i])) continue;
            swap(a[i], a[++j]);
      }
      a[r] = a[j + 1];
      a[j + 1] = x;
      quickSort!(A, L)(a, p, j);
      quickSort!(A, L)(a, j + 2, r);
}

void customSort(T)(T[] a)
{
  quickSort!(T[], less!T)(a, 0, a.length-1);
}

ulong getCycle() { asm { rdtsc; } }

ulong bench1(double[] vals)
{
  ulong startTime = getCycle();
  double[] v;
  v.length = vals.length;
  for(int i = 0; i < 100; i++)
  {
    for(int j = 0; j < v.length; j++) v[j] = vals[j];
    sort(v);
  }
  return getCycle() - startTime;
}

ulong bench2(double[] vals)
{
  ulong startTime = getCycle();
  double[] v;
  v.length = vals.length;
  for(int i = 0; i < 100; i++)
  {
    for(int j = 0; j < v.length; j++) v[j] = vals[j];
    customSort(v);
  }
  return getCycle() - startTime;
}

void main()
{
  Mt19937 gen;
  double[] vals;
  vals.length = 1000;
  for(int i = 0; i < vals.length; i++) vals[i] = uniform(0.0,1000.0);
  sort(vals[]);

  ulong time1, time2;
  for(int i = 0; i < 100; i++)
  {
    time1 += bench1(vals);
    time2 += bench2(vals);
  }
  writeln("Sorting with phobos sort: ", time1/1e5);
  writeln("Sorting with custom quickSort: ", time2/1e5);
  if(time1 > time2)
    writeln(100.0 * (time1-time2) / time1, " percent faster");
  else
    writeln(100.0 * (time2-time1) / time2, " percent slower");
}