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.