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