vault

Quicksort

12 min read

Quicksort

Quicksort is a divide-and-conquer sorting algorithm invented by Tony Hoare in 1959 (published 1962). It picks a “pivot” element from the array, partitions the remaining elements into “less than pivot” and “greater than pivot” subgroups, then recursively sorts each subgroup. It runs in O(n log n) average but O(n²) worst case, sorts in place with only O(log n) auxiliary space, and is generally the fastest comparison sort in practice on random data — which is why nearly every standard library uses some quicksort variant under the hood.

1. Intuition — Sorting by “Smaller Than the Boss”

You have a line of unruly children to sort by height.

  • Pick one child arbitrarily. Call her the pivot.
  • Tell every other child: “If you’re shorter than the pivot, stand to her left. If you’re taller, stand to her right.”
  • Now the pivot is in her final position — every child to her left is shorter, every child to her right is taller.
  • Recursively sort the left subgroup and the right subgroup.

The “magic” is that the partition step does useful work — it places one element correctly and produces two smaller, independent subproblems. The recursion handles them. There’s no merge step (unlike Merge Sort) — the algorithm sorts in place because the partition rearranges the original array.

2. Tiny Worked Example

Sort [5, 2, 8, 1, 9, 3]. Pick the last element as pivot (a common simple choice; we’ll discuss better choices below).

Pass 1: pivot = 3

Original:  [5, 2, 8, 1, 9, 3]
                          ↑pivot
Partition: walk through 5,2,8,1,9, swapping smaller-than-3 elements to the left:
  5 > 3: skip
  2 < 3: swap to position 0 → [2, 5, 8, 1, 9, 3]
  8 > 3: skip
  1 < 3: swap to position 1 → [2, 1, 8, 5, 9, 3]
  9 > 3: skip
After scan: place pivot at boundary (position 2):
  Final:    [2, 1, | 3 | 8, 5, 9]    ← 3 is now in final position

Now recurse on [2, 1] (left of pivot) and [8, 5, 9] (right of pivot).

Pass 2 (left): [2, 1], pivot = 1

[2, 1] → partition → [ | 1 | 2]

Pass 2 (right): [8, 5, 9], pivot = 9

[8, 5, 9] → partition → [8, 5, | 9 | ]

Recurse on [8, 5], pivot = 5

[8, 5] → [ | 5 | 8]

Combined result

[1, 2, 3, 5, 8, 9]

Done. Note that we never allocated a separate buffer — all the swaps happened in the original array.

3. Two Partition Schemes (Lomuto vs Hoare)

Quicksort’s correctness hinges on a correct partition routine. There are two well-known schemes:

3.1 Lomuto Partition (simpler to teach, slightly slower)

Pivot is the last element. Maintain an index i for the boundary of the “less than pivot” region; sweep j through the rest.

lomuto_partition(arr, lo, hi):
    pivot := arr[hi]
    i := lo - 1
    for j := lo to hi - 1:
        if arr[j] <= pivot:
            i := i + 1
            swap arr[i], arr[j]
    swap arr[i+1], arr[hi]
    return i + 1                # final pivot position

3.2 Hoare Partition (the original; faster, trickier)

Two pointers from each end, swapping when both find a “wrong-side” element.

hoare_partition(arr, lo, hi):
    pivot := arr[lo]            # first element as pivot (or median-of-three)
    i := lo - 1
    j := hi + 1
    loop:
        repeat: i := i + 1
        until arr[i] >= pivot
        repeat: j := j - 1
        until arr[j] <= pivot
        if i >= j:
            return j            # split point (NOT necessarily the pivot index!)
        swap arr[i], arr[j]

Subtle but important

Hoare partition’s return value is not the pivot’s final index — it’s a split point such that everything left ≤ everything right. Recursive calls go on [lo..j] and [j+1..hi], not [lo..p-1] and [p+1..hi]. Lomuto’s return is the pivot index. Don’t mix the two.

Hoare partition does ~3× fewer swaps on average, which is why it’s used in real implementations. Lomuto is easier to reason about and is what most CS courses teach.

4. Python Implementation (Lomuto, for clarity)

def quicksort(arr: list[int]) -> None:
    """In-place quicksort."""
    _qs(arr, 0, len(arr) - 1)
 
def _qs(arr, lo, hi):
    if lo < hi:
        p = _partition(arr, lo, hi)
        _qs(arr, lo, p - 1)
        _qs(arr, p + 1, hi)
 
def _partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

For Python beginners, “functional quicksort” is also a thing:

def quicksort_functional(arr):
    if len(arr) <= 1: return arr
    pivot = arr[len(arr) // 2]
    less    = [x for x in arr if x < pivot]
    equal   = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quicksort_functional(less) + equal + quicksort_functional(greater)

This is conceptually clean but not the real quicksort: it allocates O(n) per level, total O(n log n) extra memory. The whole point of “real” quicksort is in-place sorting.

5. Complexity Analysis — The Story

5.1 The Best & Average Case

Best case: every partition splits the array exactly in half. The recurrence is:

T(n) = 2 · T(n/2) + Θ(n)   ⇒   T(n) = Θ(n log n)

Same recurrence as Merge Sort; same conclusion.

Average case: even with random pivots, “expected” splits are near 50-50. Formal analysis (CLRS Ch. 7.4) gives:

E[T(n)] = Θ(n log n)

The constant is small — quicksort’s inner loop is very tight, with mostly compares and swaps and excellent cache behavior. In practice, quicksort beats merge sort by 2-3× on random data.

5.2 The Worst Case

Worst case: every partition is maximally unbalanced (e.g., pivot is always the smallest or largest element). Then one subproblem is size n-1 and the other is size 0. The recurrence becomes:

T(n) = T(n-1) + Θ(n)   ⇒   T(n) = Θ(n²)

When does this happen with naive pivoting?

  • “Always pick last element as pivot” + already-sorted input → every partition is unbalanced → O(n²). (This is why “quicksort on already-sorted input is O(n²)” is a famous gotcha.)
  • “Always pick first element” — same problem with reverse-sorted input.

This is a serious problem in practice. Sorted-or-nearly-sorted data is very common (logs, time-series, etc.). The fix is good pivot selection (next section).

5.3 Space

  • Recursion stack: O(log n) average, O(n) worst. Recursing on the smaller side first and using tail-call elimination on the larger keeps stack at O(log n) worst-case (a standard optimization).
  • Auxiliary data: O(1) — partition is in place.

So total auxiliary: O(log n) average. This beats merge sort’s O(n) and is one of quicksort’s main advantages.

6. Pivot Selection — The Make-or-Break Choice

6.1 First or Last Element

Worst case O(n²) on sorted input. Don’t use in production, but acceptable for interview blackboard code.

6.2 Random Pivot

Pick a uniformly random index in [lo..hi], swap it to the end (or wherever your partition expects), then partition. Expected O(n log n) regardless of input order. Worst case is still O(n²) but only with vanishingly small probability — adversaries can’t construct a bad input without seeing your random seed.

import random
def _qs_random(arr, lo, hi):
    if lo < hi:
        r = random.randint(lo, hi)
        arr[r], arr[hi] = arr[hi], arr[r]   # move random pick to end
        p = _partition(arr, lo, hi)
        _qs_random(arr, lo, p - 1)
        _qs_random(arr, p + 1, hi)

6.3 Median-of-Three

Pick the median of arr[lo], arr[mid], arr[hi] as pivot. Eliminates O(n²) on sorted input (the median of three elements at the extremes is reasonable). Standard in many production implementations.

6.4 Median-of-Medians (deterministic O(n) selection)

Use the Median of Medians algorithm to pick a guaranteed-good pivot in O(n). Gives worst-case O(n log n) quicksort, but the constant is large enough that it’s rarely used in practice. See Quickselect for the related selection algorithm.

6.5 Introsort (the production solution)

Start with quicksort. Track recursion depth. If depth exceeds 2 log₂ n (signaling we’re hitting the bad case), switch to Heap Sort for the remaining subproblem. Quick-sort’s average speed; heap-sort’s worst-case guarantee. This is what C++ std::sort actually does. See Intro Sort.

7. Three-Way Partitioning (Dutch National Flag)

Standard quicksort can degrade on inputs with many duplicates — equal elements all go on one side, producing imbalanced partitions. The fix is 3-way partition: split into < pivot, == pivot, > pivot, then recurse on the outer two only.

This is also called the Dutch National Flag partition (Dijkstra’s name).

def quicksort_3way(arr, lo, hi):
    if lo >= hi: return
    lt, gt = lo, hi
    pivot = arr[lo]
    i = lo
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1; i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1
    quicksort_3way(arr, lo, lt - 1)
    quicksort_3way(arr, gt + 1, hi)

For data with many duplicates, this can turn a O(n²) worst case (all duplicates collapse to one partition) into O(n) (all duplicates handled in the middle group, no recursion).

8. Quickselect — A Variant for Top-K

If you only need the k-th smallest (not the full sort), you don’t need to recurse on both sides — only the side containing index k. This gives an algorithm running in O(n) average (still O(n²) worst), called Quickselect.

def quickselect(arr, k):
    """Return k-th smallest element (0-indexed)."""
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        p = _partition(arr, lo, hi)
        if   p == k:  return arr[k]
        elif p <  k:  lo = p + 1
        else:         hi = p - 1
    return arr[lo]

This is the standard interview answer to “find the k-th largest element in an array” (you can also use a heap of size k for O(n log k), but quickselect is asymptotically better at O(n)).

9. When To Use Quicksort

9.1 Use it when:

  • You have random or near-random data — quicksort’s average case dominates.
  • You need in-place sorting (memory-constrained).
  • Your platform’s standard library uses quicksort (introsort) and you’re calling sort() — you’re already using it.
  • You’re solving a selection problem (k-th smallest, top-k) — quickselect is the answer.

9.2 Don’t use it when:

  • You need stability — quicksort is not stable; use Merge Sort or Tim Sort.
  • You need worst-case O(n log n) — use Merge Sort or Heap Sort (or Intro Sort).
  • You’re sorting a linked list — use merge sort.
  • The data is mostly sorted with a few items out of place — use Tim Sort (O(n) on sorted prefixes).

10. Pitfalls

10.1 Picking the First/Last Element on Sorted Input

The O(n²) worst case bites in production. Always randomize or use median-of-three.

10.2 Forgetting to Move the Pivot Back

After Lomuto partitioning, you must swap the pivot into its final position (swap arr[i+1], arr[hi]). Forgetting this is a silent bug.

10.3 Using < vs <= in Partition

In Lomuto, if arr[j] <= pivot (≤ not <) is needed to handle duplicates correctly when pivot is at hi. Subtle bugs creep in if you flip this.

10.4 Stack Overflow on Adversarial Input

Even with a random pivot, you’ll occasionally see deep recursion. Use introsort (depth limit + switch to heap sort) to bound the worst case, or convert tail recursion to iteration.

10.5 Confusing Hoare’s Return Value With Lomuto’s

Hoare returns a split point, Lomuto returns the pivot index. The recursive calls differ:

  • Lomuto: qs(lo, p-1); qs(p+1, hi) (pivot is at p, in final place)
  • Hoare: qs(lo, p); qs(p+1, hi) (pivot is somewhere on the left of p+1, not necessarily fixed)

10.6 Stability Misconception

Quicksort is not stable. Equal elements may be reordered. If your interviewer asks “is your sort stable?” — say no, then explain when stability matters.

11. Diagram — The Recursion Tree (Average Case)

flowchart TD
  N["[5,2,8,1,9,3,7,4]<br/>pivot ≈ median, balanced split"]
  N --> L["[1,2,3]<br/>+ pivot"]
  N --> R["[7,8,9]<br/>+ pivot"]
  L --> LL["[1]"]
  L --> LR["[3]"]
  R --> RL["[7]"]
  R --> RR["[9]"]

What this diagram shows. A near-balanced quicksort recursion: each level processes Θ(n) total elements (across all subproblems), and the tree has log₂ n levels — total Θ(n log n). When pivot selection goes bad, the tree degenerates into a long chain of size-1-vs-(n-1) splits, giving Θ(n²).

12. Quicksort vs Merge Sort vs Heap Sort

PropertyQuicksortMerge SortHeap Sort
Worst timeO(n²)O(n log n)O(n log n)
Average timeO(n log n), small constantO(n log n), larger constantO(n log n), large constant
Auxiliary spaceO(log n)O(n)O(1)
Stable?❌✅❌
In-place?✅❌✅
Cache behaviorExcellent (sequential access)GoodPoor (heap accesses jump)
Used byC qsort, C++ std::sort (introsort)Python sorted (Tim sort), Java Object[]Embedded systems, real-time

The reason quicksort dominates production despite the O(n²) worst case: with randomization or introsort, the worst case never bites, and the constant factor on the average case is the smallest of the three.

13. Open Questions

  • How does Hoare’s partition perform vs Lomuto’s on cache-bound modern CPUs? Older folklore says Hoare is ~3× faster in swap count; modern measurements may differ.
  • What’s the optimal switch-to-insertion-sort threshold for small subarrays? Standard advice is 10-20 elements; modern std libs may differ.

14. See Also

Graph View

Backlinks