private const int _maxspan = 7;	// subarrays of _maxspan or fewer elements
				// will be sorted by a simple insertion sort

private
{
  template DefaultComparer(Elem)
  {
    int DefaultComparer(inout Elem a, inout Elem b)
    {
      return typeid(Elem).compare(cast(void*)&a, cast(void*)&b);
    }
  }

  private template DefaultSwapper(Elem)
  {
    void DefaultSwapper(inout Elem a, inout Elem b)
    {
      typeid(Elem).swap(cast(void*)&a, cast(void*)&b);
    }
  }
}

template sort(Elem)
{
  alias .sort!(Elem, .DefaultComparer!(Elem)) sort;
}

template sort(Elem, alias Compare)
{
  alias .sort!(Elem, Compare, .DefaultSwapper!(Elem)) sort;
}

template sort(Elem, alias Compare, alias Swap)
{
  void sort(inout Elem[] a)
  {
    Elem* base;
    Elem*[40] stack;		// stack
    Elem** sp;		        // stack pointer
    Elem* i, j, limit;		// scan and limit pointers
    uint thresh;                  // size of _maxspan elements in bytes

    base = &a[0];
    thresh = _maxspan;                     // init threshold
    sp = stack;                            // init stack pointer
    limit = base + a.length;        	 // pointer past end of array
    while (1)                              // repeat until done then return
    {
      while (limit - base > thresh)        // if more than _maxspan elements
      {
        //swap middle, base
        version (none)
        {
          // Doesn't seem to actually DO anything.
          // Both arguments will always be the same pointer. --andy
          Swap(*((cast(uint)(limit - base) >> 1) -
                 (cast(uint)(limit - base) >> 1) + base), *base);
        }

        i = base + 1;    			// i scans from left to right
        j = limit - 1;    		// j scans from right to left

        if (Compare(*i, *j) > 0)		// Sedgewick's
          Swap(*i, *j);			//    three-element sort
        if (Compare(*base, *j) > 0)	// sets things up
          Swap(*base, *j);		// so that
        if (Compare(*i, *base) > 0)	// *i <= *base <= *j
          Swap(*i, *base);		// *base is the pivot element

        while (1)
        {
          do				// move i right until *i >= pivot
            i ++;
          while (Compare(*i, *base) < 0);
          do				// move j left until *j <= pivot
            j --;
          while (Compare(*j, *base) > 0);
          if (i > j)			// break loop if pointers crossed
            break;
          Swap(*i, *j);			// else swap elements, keep scanning
        }
        Swap(*base, *j);			// move pivot into correct place
        if (j - base > limit - i)		// if left subarray is larger...
        {
          sp[0] = base;			// stack left subarray base
          sp[1] = j;			//    and limit
          base = i;			// sort the right subarray
        }
        else				// else right subarray is larger
        {
          sp[0] = i;			// stack right subarray base
          sp[1] = limit;			//    and limit
          limit = j;			// sort the left subarray
        }
        sp += 2;				// increment stack pointer
        assert(sp < cast(Elem**)stack + stack.length);
      }

      // Insertion sort on remaining subarray
      i = base + 1;
      while (i < limit)
      {
        j = i;
        while (j > base && Compare(*(j - 1), *j) > 0)
        {
          Swap(*(j - 1), *j);
          j --;
        }
        i ++;
      }

      if (sp > stack)			// if any entries on stack...
      {
        sp -= 2;				// pop the base and limit
        base = sp[0];
        limit = sp[1];
      }
      else				// else stack empty, all done
        return *cast(long*)(&a);
    }
  }
}

import std.string;

unittest
{
    debug(qsort) printf("array.sort.unittest()\n");

    int a[] = new int[10];

    a[0] = 23;
    a[1] = 1;
    a[2] = 64;
    a[3] = 5;
    a[4] = 6;
    a[5] = 5;
    a[6] = 17;
    a[7] = 3;
    a[8] = 0;
    a[9] = -1;

    //a.sort;
    sort!(int)(a);

    for (int i = 0; i < a.length - 1; i++)
    {
	debug(qsort) printf("i = %d", i);
	debug(qsort) printf(" %d %d\n", a[i], a[i + 1]);
	assert(a[i] <= a[i + 1]);
    }

    debug(qsort) printf("Take 2\n");

    class TestInteger {
      int value;
      this(int i) {
        value = i;
      }

      char[] toString() {
        return std.string.toString(value);
      }

      override int opCmp(Object r) {
        TestInteger rhs = cast(TestInteger)r;
        assert(rhs !== null);

        return value - rhs.value;
      }

      override int opEquals(Object r) {
        TestInteger rhs = cast(TestInteger)r;

        return rhs !== null && value == rhs.value;
      }
    }

    TestInteger[] b;
    b ~= new TestInteger(23);
    b ~= new TestInteger(1);
    b ~= new TestInteger(64);
    b ~= new TestInteger(5);
    b ~= new TestInteger(6);
    b ~= new TestInteger(5);
    b ~= new TestInteger(17);
    b ~= new TestInteger(3);
    b ~= new TestInteger(0);
    b ~= new TestInteger(-1);

    sort!(TestInteger)(b);

    for (int i = 0; i < a.length - 1; i++)
    {
	debug(qsort) printf("i = %d", i);
	debug(qsort) printf(" %.*s %.*s\n", b[i].toString(), b[i + 1].toString());
	//assert(b[i] <= b[i + 1]);
    }

    debug(qsort) printf("Unit test passed.\n");
}

debug (main) int main() { return 0; }