QuickSort(A[1, ..., n], lo, hi)

Input: An array A of n distinct integers, the lower index and the higher index

// For the first call lo = 1 and hi = n

Output: The array A in sorted order

If lo = hi return

// The array A is already sorted in this case

If lo > hi or indices out of the range 1 to n then return

Else

Pick an index k in [lo,hi] as the pivot

// Assume that this can be done using O(1) cells on the stack

i = Partition(A[lo, ..., hi], k)

// Use in-place partitioning here so assume that this can be done

// using O(1) space on the stack

If i - lo <= hi - i

QuickSort(A, lo, i-1) // sort the smaller half first

QuickSort(A, i+1, hi)

Else

QuickSort(A, i+1, hi) // sort the smaller half first

QuickSort(A, lo, i-1)

What is the space complexity if tail recursion is not used and pivots are chosen adversarially? What is the space complexity if tail recursion is not used and pivots are chosen uniformly at random?