Quicksort

Why it costs this much

A good pivot splits the input roughly in half, giving about log n levels of partitioning with O(n) work at each level.

Code

def quicksort(a):     # readable version: O(n) extra space; in-place uses O(log n)
    if len(a) <= 1:
        return a
    pivot = a[len(a) // 2]
    left  = [x for x in a if x < pivot]
    mid   = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]
    return quicksort(left) + mid + quicksort(right)   # ~log n levels, O(n) each

Common pitfalls

A bad pivot, such as always taking the first item of sorted input, gives n levels and Θ(n²). Random or median-of-three pivots avoid this. Quicksort is not stable.

Operation by operation

Quicksort. Average assumes a pivot that splits input reasonably, such as a random pivot. Not stable. A first-element pivot on sorted input is the classic worst case. Recurse into the smaller half first to bound the stack at O(log n).