Sorting9 min read

Quick Sort

Pick a pivot, split the crowd — everyone shorter left, taller right
average case:\(O(n \log n)\)worst case:\(O(n^2)\) — bad pivotspace:\(O(\log n)\) stackin-place:Yes

Imagine organizing a crowd of people by height. You pick one person — the pivot — and ask everyone to stand left if they're shorter, right if they're taller. Now the pivot is in their exact final position. Repeat the process on the left crowd and the right crowd separately. That's quicksort: pick, partition, recurse.

It's fast in practice because partitioning is a single fast pass through contiguous memory (cache-friendly!), and on average the pivot lands near the middle, giving balanced recursion.

The Partition Step

Lomuto partition (simpler to understand): Pick the last element as pivot. Walk a pointer i from the left; whenever you find an element ≤ pivot, swap it with position i and advance i. Finally swap the pivot into position i. Easy to write, slightly more swaps.

Hoare partition (faster in practice): Two pointers start at opposite ends. Left pointer advances while it sees elements ≤ pivot; right pointer retreats while it sees elements ≥ pivot. When both stall, swap them and continue until the pointers cross. About 3× fewer swaps than Lomuto on random input.

Pivot Choice — Everything Depends on This

First or last element: Catastrophically bad on already-sorted or reverse-sorted input. Every partition produces one empty side → \(O(n^2)\) depth.

Random pivot: Pick a random index and swap it into position before partitioning. Randomness makes the \(O(n^2)\) worst case astronomically unlikely — the probability of consistently bad pivots is (2/n)^n.

Median-of-three: Look at first, middle, and last elements; use the median as pivot. Cheap, eliminates the sorted-input pathology, no random number needed.

Average Case \(O(n \log n)\) — Why It Works

With a random pivot, a pivot that lands in the middle 50% of values (which happens with probability 1/2) creates a split no worse than 25%-75%. The resulting recursion depth is still \(O(\log n)\) in expectation. More precisely, the expected total comparisons is about 2n ln n ≈ 1.39 n \(\log_2\)n — roughly 39% more comparisons than merge sort's n \(\log_2\)n, but with much better cache behavior in practice.

Introsort — The Real-World Best of Both

All major standard libraries use Introsort: start with quicksort, monitor recursion depth, and switch to heapsort if depth exceeds 2·log n. This gives \(O(n \log n)\) worst case while keeping quicksort's excellent average performance. For small sub-arrays (n ≤ ~32), they also switch to insertion sort. C++ std::sort, Java's Arrays.sort for primitives, and Rust's slice::sort_unstable all use Introsort variants.

Note: Quicksort vs Merge sort: quicksort wins in practice because partitioning scans memory sequentially (cache-friendly) and requires no extra array. Merge sort wins on paper: stable, \(O(n \log n)\) guaranteed, \(O(n)\) space. In practice, randomized quicksort is the default for in-memory sorting.

Quick Sort — Lomuto Partition

import random


def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)


def partition(arr, lo, hi):
    # Random pivot for O(n²) worst-case avoidance
    r = random.randint(lo, hi)
    arr[r], arr[hi] = arr[hi], arr[r]
    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


data = [10, 7, 8, 9, 1, 5]
quicksort(data)
print(data)
Output
[1, 5, 7, 8, 9, 10]

Complexity

🚀 Average caseExpected with random pivot — ~1.39× merge sort's comparisons but better cache
Linearithmic — fast in practice\(O(n \log n)\)
💀 Worst caseSorted/reverse-sorted input with first/last pivot — use random pivot to avoid
Quadratic — every pivot is extreme\(O(n^2)\)
📦 Space (stack)In-place — only recursion stack; \(O(n)\) worst case without tail recursion optimization
Logarithmic on average\(O(\log n)\)
⚡ Partition stepSequential memory scan — excellent cache behavior
Linear scan of current range\(O(n)\)

Quick check

What input pattern triggers quicksort's \(O(n^2)\) worst case when using the last element as pivot?

Continue reading

Merge Sort
Split, sort each half, merge — guaranteed \(O(n \log n)\) every time
→
QuickSelect
Find the kth smallest without fully sorting
→
Randomized Quick Sort
A random pivot destroys adversarial worst-case inputs
→