QSort in D: is this best?

[Lutger]

downs wrote:

> 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 see, that's clever.

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

I didn't see you second post. But this is quite funny, you could write the  
same page the haskell intro does but swap the roles of haskell and C (or D) 
:)