the array to be sorted
a 2-parameter
function returning a number n, telling if the 1st parameter is
less-than (n < 0), equal (n == 0) or greater than the 2nd (n > 0)
a 1-parameter function returning an element of the array
the array is sorted in place
Sorts the array
anArrayaccording to the comparatoraCmpFunusing a quick sort (https://en.wikipedia.org/wiki/Quicksort), but in place, and using a so-called 'tail-recursion'. The parameteraPickFuntells how to choose the pivot for splitting the array.anArrayis sorted in place, and hence is modified by this function.The algorithm itself is described in the Cormen, chapter 7.1.
Despite the way it is named in the Cormen, it is not a tail-recursive function. Simply, it is an optimization of the basic quicksort algorithm that does 2 recursive calls, one of which is tail-recursive, and it unrolls this call into a loop. Basically, it removes half of the recursive calls.
The function is also optimized to always select the smallest array for the recursive calls. So that the callstack maximal size cannot exceed O(log(n)) where n is the length of
anArray(hence also admitting that all the recursive calls are not eliminated in this function).For more information, consult the chapters 7.1and 7.4 of the Cormen.