QSort in D: is this best?

[downs]

Lutger wrote:
> downs wrote:
> 
>> Or are there any bugs/optimization opportunities I'm missing?
>>
>> void qsort(T)(T[] array) {
>>   if (array.length < 2) return;
>>   static int i;
>>   auto pivot = array[i++%$];
>>   // from is base-0, to is base-1.
>>   int from = 0, to = array.length;
>>   while (from != to) {
>>     if (array[from] >= pivot && array[to-1] < pivot)
>>       swap(array[from], array[to-1]);
>>     if (array[from] < pivot)
>>       from ++;
>>     if (array[to-1] >= pivot)
>>       to --;
>>   }
>>   array[0 .. from].qsort();
>>   array[from .. $].qsort();
>> }
> 
> It's not reentrant but perhaps you don't care?
> 

Given that i is used as semi-random state, cross-thread bugs would help rather than hurt it, by making it more unpredictable.

> I think these two optimizations matter the most:
> - improve selection of pivot (median of 3 for example)
> - switch to insertion sort or shellsort when array is below a certain length 
> (somewhere between 50 and 150 I think is ok). 
> 
> A further optimization can be to implement a custom stack, but it's not as 
> much bang-for-buck as switching to a different sort.
> 
> 

Well yeah, it's not the best sorting algorithm all things considered. I intended it mostly as a response to the much-vaunted Haskell qsort example.