Quick sort is the rockstar of sorting algorithms. Invented by Tony Hoare in 1959, it dominates real-world sorting libraries. It's a classic divide and conquer algorithm, an in-place sort, and when tuned properly, it's frequently the fastest comparison-based sort on real hardware.

Why do practitioners adore quick sort even though merge sort has the same average complexity? Two reasons: it sorts inside the original array, and it plays beautifully with the CPU cache. Those properties turn O(n log n) on paper into actually fast in production.

How It Works

Quick sort follows three simple steps, applied recursively:

1. Pick a pivot — choose any element from the array.

2. Partition — rearrange so everything smaller than the pivot sits left and everything larger sits right. The pivot is now in its final sorted position.

3. Recurse — quick sort the left subarray, then the right.

Let's walk through [10, 7, 8, 9, 1, 5] using the last element as pivot:

Pivot = 5. After partitioning: [1, 5, 8, 9, 10, 7]. The 5 is locked in place.

Recurse left on [1] — already sorted.

Recurse right on [8, 9, 10, 7]. Pivot = 7 → [7, 9, 10, 8]. Locked.

Recurse on [9, 10, 8]. Pivot = 8 → [8, 10, 9]. Locked.

Recurse on [10, 9]. Pivot = 9 → [9, 10]. Done.

Final: [1, 5, 7, 8, 9, 10]. Nothing was copied — every element moved via in-place swaps.

Choosing a Pivot

The pivot is everything. A good pivot splits the array roughly in half; a bad one splits it 1 vs n-1 and you fall off the cliff into O(n^2).

First or last element — simplest, but if input is already sorted (or reverse sorted), every partition is maximally unbalanced. Hello, worst case. 💀

Middle element — better for sorted-ish data, but adversaries can still construct pathological inputs.

Random pivot — this is randomized quicksort. No specific input can reliably trigger worst case because the attacker can't predict your RNG.

Median-of-three — sample the first, middle, and last elements; use their median. Cheap and resistant to most pre-sorted inputs. This is what most production libraries do.

The "already-sorted with naive pivot" trap is the classic gotcha. A junior dev writes pivot = arr[0], runs it on sorted user data, and watches the server time out.

Lomuto vs Hoare Partition

Lomuto partition (used in our partition function) keeps a pointer i for the boundary of the "less than pivot" region, scans with j, and swaps when it finds a smaller element. Easy to teach — but it does roughly 3x more swaps than Hoare and degrades horribly on arrays with many duplicates.

Hoare partition (Tony's original) uses two pointers moving toward each other from both ends, swapping pairs on the wrong side. Fewer swaps, handles duplicates better, but the index it returns isn't the pivot's final position — so recursion bounds differ.

Tradeoff: Lomuto is cleaner code, Hoare is faster. Production implementations often use a three-way partition algorithm (Dutch National Flag) for duplicate-heavy data.

Complexity Analysis

Property	Value
Best case time	O(n log n)
Average case time	O(n log n)
Worst case time	O(n^2)
Space (in-place)	O(log n) stack
Stable?	No ❌
In-place?	Yes ✅

The worst case happens when every pivot is the smallest or largest element. Randomized pivot selection makes this vanishingly unlikely.

Why Quick Sort Wins in Practice

Merge sort and quick sort both average O(n log n), so why is quick sort the default in so many languages?

Cache locality: it works on contiguous slices of the original array. Modern CPUs love sequential memory access; merge sort jumps between source and destination buffers.

In-place: no auxiliary array means no extra allocations and no garbage collection pressure.

Low constant factors: the inner partition loop is just a comparison and a swap — tight, branch-predictable, compiler-friendly.

Merge sort wins when stability matters or when sorting linked lists. Quick sort wins almost everywhere else on arrays.

Common Pitfalls

Bad pivot causes $O(n^2)$: using arr[0] on sorted data is the classic trap. Always randomize or use median-of-three.

Stack overflow on already-sorted input: recursion depth becomes n in the worst case. Python's default recursion limit (~1000) will blow up on a sorted array of 10,000 elements.

Off-by-one in partition: the boundary pointer and final swap are easy to get wrong. Test with [1], [1, 1], and [2, 1] before trusting your code.

Instability surprises: equal elements may swap positions. Sorting (name, age) tuples by age does not preserve original name order.

Recursing on the larger half wastes stack: always recurse on the smaller partition first and tail-iterate on the larger one. This bounds stack depth to O(log n) even in degenerate cases.

Real-World Uses

C's `qsort` in glibc uses a quicksort variant with median-of-three pivot.

Java's `Arrays.sort` for primitives uses dual-pivot quicksort (Yaroslavskiy's variant), which often beats classical single-pivot quicksort.

C++ STL `std::sort` uses introsort — a hybrid that starts with quicksort, switches to heapsort if recursion gets too deep, and uses insertion sort for small subarrays.

Rust's `sort_unstable` uses pdqsort (pattern-defeating quicksort).

Randomized quicksort is preferred in security-sensitive contexts: it can't be triggered into worst-case behavior by malicious input.

Quick Sort vs Merge Sort

Situation	Winner
Sorting arrays in memory	Quick sort (cache-friendly, in-place)
Stability required	Merge sort
Sorting linked lists	Merge sort
External sort (data on disk)	Merge sort (sequential I/O)
Worst-case guarantees needed	Merge sort or introsort
Smallest memory footprint	Quick sort

Frequently Asked Questions

Is quick sort stable?

No. The partition step swaps elements across long distances, scrambling the original order of equal keys. Use merge sort or Python's sorted() when stability matters.

Why does Python not use quick sort?

Python's sorted() and list.sort() use Timsort, a hybrid of merge sort and insertion sort. Timsort is stable, exploits pre-existing runs of sorted data, and guarantees O(n log n) worst case.

How is randomized quicksort different?

It picks the pivot uniformly at random. Expected runtime stays O(n log n) regardless of input, and no specific input can force worst case — crucial when sorting untrusted data.

What is introsort?

A hybrid: it starts as quicksort, but if recursion depth exceeds 2 log_2 n, it switches to heapsort to guarantee O(n log n) worst case. For tiny subarrays it falls back to insertion sort. C++ std::sort uses introsort.

Can quick sort be done iteratively?

Yes — replace recursion with an explicit stack of (low, high) pairs. Push the larger partition first and process the smaller one immediately to keep the stack shallow.

Why is the worst case $O(n^2)$?

If the pivot is always the smallest (or largest) element, each partition only removes one element, giving n levels of n-element scans. Randomization or median-of-three reduces this to essentially zero probability.

Quick Sort in Python

Try it yourself

How it works

How It Works

Choosing a Pivot

Lomuto vs Hoare Partition

Complexity Analysis

Why Quick Sort Wins in Practice

Common Pitfalls

Real-World Uses

Quick Sort vs Merge Sort

Frequently Asked Questions

Related examples

Merge Sort in Python

Bubble Sort in Python

Insertion Sort in Python

Selection Sort in Python