Quick Sort

Intuition

Picture a PE teacher lining up a class by height. Instead of comparing every pair of students, the teacher picks one student, call her the pivot, and says: everyone shorter stand on her left, everyone taller on her right. After that single sweep, the pivot is standing in exactly the spot she will occupy in the final line. Now the teacher repeats the same trick inside the left group and inside the right group, independently.

That is quick sort. Where merge sort does the easy part first (split blindly) and the real work on the way back (merge), quick sort does the real work up front (partition) and needs no combine step at all. Once both sides are sorted, the whole array is sorted, because everything left of the pivot was already smaller than everything right of it.

How it works step by step

1. If the range [lo, hi] has fewer than two elements, return.
2. Choose a pivot. Picking a random index and swapping it to hi protects against worst-case inputs.
3. Partition (Lomuto scheme): keep a store index starting at lo. Scan j from lo to hi - 1; whenever a[j] < pivot, swap a[j] into position store and increment store.
4. Swap the pivot from hi into store. Now everything left of store is smaller and everything right is greater or equal.
5. Recursively sort [lo, store - 1] and [store + 1, hi]. The pivot itself is never touched again.

Dry run

Partition [7, 2, 9, 4, 3, 8, 5] with the last element 5 as the pivot (no randomisation, so the trace is predictable).

The pivot 5 is now at index 3, its final position. The left part [2, 4, 3] and the right part [9, 8, 7] are sorted by the same procedure, and nothing ever needs to cross the pivot again.

Code

This Java version uses a random pivot and recurses only into the smaller side while looping on the larger one. That small change caps the recursion depth at O(log n) even in unlucky cases, so it cannot overflow the stack.

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

public class QuickSort {
    public static void sort(int[] a) {
        quickSort(a, 0, a.length - 1);
    }

    private static void quickSort(int[] a, int lo, int hi) {
        while (lo < hi) {
            int p = partition(a, lo, hi);
            // recurse on the smaller side, loop on the larger one
            if (p - lo < hi - p) {
                quickSort(a, lo, p - 1);
                lo = p + 1;
            } else {
                quickSort(a, p + 1, hi);
                hi = p - 1;
            }
        }
    }

    private static int partition(int[] a, int lo, int hi) {
        int r = ThreadLocalRandom.current().nextInt(lo, hi + 1);
        swap(a, r, hi);
        int pivot = a[hi];
        int store = lo;
        for (int j = lo; j < hi; j++) {
            if (a[j] < pivot) swap(a, store++, j);
        }
        swap(a, store, hi);
        return store;
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        int[] a = {7, 2, 9, 4, 3, 8, 5};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}

import random


def quick_sort(a, lo=0, hi=None):
    """Sorts list a in place."""
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)
        if p - lo < hi - p:
            quick_sort(a, lo, p - 1)
            lo = p + 1
        else:
            quick_sort(a, p + 1, hi)
            hi = p - 1


def partition(a, lo, hi):
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]
    pivot = a[hi]
    store = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[store], a[j] = a[j], a[store]
            store += 1
    a[store], a[hi] = a[hi], a[store]
    return store


nums = [7, 2, 9, 4, 3, 8, 5]
quick_sort(nums)
print(nums)

Time and space complexity

Each partition is a linear scan. If pivots split the range roughly in half, there are about log n levels of linear work. If the pivot is always the smallest or largest element, one side is empty and the other has n - 1 elements, so the levels become n, n - 1, n - 2 and the total is quadratic. A random pivot makes that disaster astronomically unlikely on any fixed input; it is no longer about the data, only about bad luck.

Edge cases

• Empty or single-element array: lo < hi is false, nothing happens.
• Already sorted or reverse sorted input: catastrophic with a fixed first or last pivot, fine with a random one.
• All elements equal: Lomuto puts every element on one side, which degrades to O(n^2). Use a three-way partition when duplicates are common.
• Two elements: partition still works; verify your bounds with this case.
• Huge inputs: without smaller-side recursion or a depth limit, a bad run can throw a stack overflow.

Common mistakes

• Always picking the first or last element as the pivot. Sorted input, a very common test case, then hits the O(n^2) worst case.
• Including the pivot in a recursive call. Recursing on [lo, p] instead of [lo, p - 1] can loop forever when the pivot is the maximum.
• Mixing Lomuto and Hoare. Hoare partitioning returns a split index where the pivot is not necessarily in its final slot, so the recursion is [lo, p] and [p + 1, hi]. Using Lomuto bounds with Hoare's partition, or the reverse, breaks the sort.
• Forgetting the final pivot swap. Without it, the pivot stays at hi and the left and right parts are not separated correctly.
• Claiming quick sort is stable. Long-distance swaps reorder equal keys; it is not stable.

Variations and when to use it

Hoare partitioning walks two pointers inward and does about three times fewer swaps than Lomuto. Three-way partitioning (the Dutch national flag idea) splits into less than, equal to, and greater than the pivot, so arrays with many duplicates sort in near-linear time. Introsort, used by C++ std::sort, starts as quick sort and switches to heap sort if recursion gets too deep, guaranteeing O(n log n). Java's Arrays.sort for primitives uses dual-pivot quick sort.

The partition routine is also a tool by itself. Quickselect partitions once and recurses into only the side that contains index k, finding the k-th smallest element in O(n) average time. Use quick sort for in-memory arrays of primitives when you want speed and low memory and do not need stability; use partitioning alone for selection and top-k problems.

Related LeetCode problems

• #912 Sort an Array — implement randomized quick sort with three-way partitioning to survive the duplicate-heavy tests.
• #215 Kth Largest Element in an Array — quickselect: partition, then recurse only toward index n - k.
• #75 Sort Colors — a single three-way partition with pivot value 1.
• #973 K Closest Points to Origin — quickselect on squared distance to find the k smallest.
• #347 Top K Frequent Elements — count frequencies, then quickselect on the counts.
• #2161 Partition Array According to Given Pivot — a stable version of the partition step.

FAQ