Quick sort. Unstable, O(N log N) time average, worst
case, O(log N) space, small constant term in time complexity.
In this implementation, the following steps are taken to avoid the
O(N<sup>2</sup>) worst case of naive quick sorts:
1. At each recursion, the median of the first, middle and last elements of
the array is used as the pivot.
2. To handle the case of few unique elements, the "Fit Pivot" technique
previously decribed by Andrei Alexandrescu is used. This allows
reasonable performance with few unique elements, with zero overhead
in other cases.
3. After a much larger than expected amount of recursion has occured,
this function transitions to a heap sort. This guarantees an O(N log N)
worst case.
Quick sort. Unstable, O(N log N) time average, worst case, O(log N) space, small constant term in time complexity.
In this implementation, the following steps are taken to avoid the O(N<sup>2</sup>) worst case of naive quick sorts:
1. At each recursion, the median of the first, middle and last elements of the array is used as the pivot.
2. To handle the case of few unique elements, the "Fit Pivot" technique previously decribed by Andrei Alexandrescu is used. This allows reasonable performance with few unique elements, with zero overhead in other cases.
3. After a much larger than expected amount of recursion has occured, this function transitions to a heap sort. This guarantees an O(N log N) worst case.