• Sorts the array anArray according to the comparator aCmpFun using a quick sort (https://en.wikipedia.org/wiki/Quicksort), but in place, and using a so-called 'tail-recursion'. The parameter aPickFun tells how to choose the pivot for splitting the array. anArray is 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.

    Parameters

    • anArray: any[]

      the array to be sorted

    • aCmpFun: ((a1: any, a2: any) => number)

      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)

        • (a1, a2): number
        • Parameters

          • a1: any
          • a2: any

          Returns number

    • aPickFun: ((a1: any[]) => any) = medianPick

      a 1-parameter function returning an element of the array

        • (a1): any
        • Parameters

          • a1: any[]

          Returns any

    Returns void

    the array is sorted in place