Quicksort

Quicksort partitions around a pivot and recurses on each side; O(n log n) on average with excellent constants, though O(n^2) in the worst case.

Partition around a pivot

Quicksort picks a pivot element and partitions the array so that everything smaller comes before it and everything larger comes after. The pivot is then in its final sorted position, and the algorithm recurses on the two sides. Unlike merge sort, all the work happens in the partition, before the recursion, and it is done in place.

Average versus worst case

When the pivot splits the array into roughly equal halves, the recursion is log n deep with O(n) partition work per level, giving O(n log n). But a consistently bad pivot, such as always choosing the first element on already-sorted data, produces splits of size n-1 and 1, degrading to O(n^2). Good pivot selection is what keeps quicksort fast.

• Best and average time: O(n log n)
• Worst case: O(n^2)
• Extra space: O(log n) for the recursion stack
• Stable: no; in place: yes

Choosing a pivot

Practical implementations avoid the worst case with median-of-three pivots or a randomly chosen pivot, which makes adversarial inputs improbable. Introsort, used in many standard libraries, monitors recursion depth and switches to heapsort if it grows too large, guaranteeing O(n log n) worst case while keeping quicksort's speed.

def quicksort(a, lo, hi):
    if lo >= hi: return
    pivot = a[(lo + hi) // 2]
    i, j = lo, hi
    while i <= j:
        while a[i] < pivot: i += 1
        while a[j] > pivot: j -= 1
        if i <= j:
            a[i], a[j] = a[j], a[i]
            i += 1; j -= 1
    quicksort(a, lo, j)
    quicksort(a, i, hi)

Why it is the default

Despite the theoretical worst case, quicksort's small constant factors and in-place operation make it the fastest general comparison sort in practice, which is why it or a hybrid based on it backs most standard-library sorts for primitive types.