Efficiency of quick sort

Quick sort picks a pivot, partitions the array so that smaller elements are on its left and larger ones on its right, then sorts both parts recursively. Partitioning n elements takes n − 1 comparisons, i.e. O(n).

Let T(n) be the time to sort n elements and let the pivot end at position k.

T(n) = T(k) + T(n − k − 1) + cn

Best case (pivot splits the array in the middle)

T(n) = 2T(n/2) + cn

Expanding: T(n) = 2[2T(n/4) + cn/2] + cn = 4T(n/4) + 2cn = ... = 2ʲ T(n/2ʲ) + j·cn.

The recursion stops when n/2ʲ = 1, i.e. j = log₂ n, so T(n) = n·T(1) + cn·log₂ n = O(n log n).

Another view: there are log₂ n levels of recursion and each level does about n comparisons in total, giving n log₂ n.

Average case

For random data the pivot lands at every position with equal probability: T(n) = (1/n) Σₖ [T(k) + T(n−k−1)] + cn, whose solution is about 1.39·n·log₂ n, still O(n log n).

Worst case

The array is already sorted (first element as pivot): one part is empty and the other has n − 1 elements, so T(n) = T(n−1) + cn = c(n + (n−1) + ... + 1) = cn(n+1)/2 = O(n²).

Choosing the median-of-three or a random pivot makes the worst case very unlikely. Extra space is O(log n) for the recursion stack.