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) :)