SortingAlgorithmaka quicksort, partition-exchange sort

Quick Sort

Pick a pivot, partition elements into smaller and larger sides, and recursively sort each side.

▶ Visualize Pattern: Two Pointers Practice (3)

Progress

Overview

Quick sort chooses a pivot, Partitioning the array so every element left of the pivot is ≤ it and every element right is ≥ it, then sorts the two sides recursively. The pivot never moves again. Average time is O(n log n) with a small constant and excellent cache behaviour; it is in-place (O(log n) stack) but not stable.

The worst case is O(n²) when pivots are consistently extreme (e.g. first-element pivot on sorted input). Production sorts guard against this: C++ std::sort uses introsort (quick sort that switches to Heap Sort when recursion gets too deep and to Insertion Sort for small ranges); Go and Rust use pdqsort, a pattern-defeating variant. Java uses dual-pivot quick sort for primitives.

comparisonO(n log n)in-placeunstablepartitioncache-friendly

Intuition

A mental model before the formal terms.

Line up people by height by picking one person as a reference and asking everyone shorter to move to their left and everyone taller to their right. The reference person is now in exactly the right spot forever. Now do the same thing separately on the left group and the right group. Good references (near the median) split groups evenly, so the job finishes in about log₂ n rounds.

How it works

If the range has fewer than two elements, return.
Choose a pivot: random index, median-of-three (a[lo], a[mid], a[hi]), or the middle element. Swap it to a[hi] for Lomuto or keep it as a value for Hoare.
Lomuto partition: i = lo; for each j in [lo, hi), if a[j] < pivot, swap a[i] and a[j] and increment i. Finally swap the pivot into a[i]; i is its final position.
Recurse on [lo, i - 1] and [i + 1, hi]. Recurse on the smaller side first and loop on the larger to cap stack depth at O(log n).
With many duplicates, use 3-way (Dutch national flag) partitioning into < pivot, == pivot, > pivot regions.

Why it works

Partition invariant (Lomuto): a[lo..i-1] < pivot, a[i..j-1] ≥ pivot, a[j..hi-1] unprocessed. When j reaches hi, swapping the pivot into i puts it between the two classes — its final sorted position.

Correctness follows by induction on range length: each side is sorted independently and every element in the left side is ≤ pivot ≤ every element in the right side.

Expected cost with random pivots: each pair of elements is compared at most once, and the probability that the i-th and j-th smallest are compared is 2/(j - i + 1), summing to about 2n ln n.

Recognition

How to tell a problem wants this.

A general-purpose in-memory sort where average speed and low memory matter and stability does not.
Problems that reduce to partitioning around a value: k-th element (Quickselect), Dutch national flag, move zeroes.
Asked about worst-case behaviour, pivot selection, or why library sorts are hybrids.

“sorted array” → Two Pointers “merge k sorted” → Divide and Conquer

Interactive visualization

Play, step, change the input. ← → and space work too.

Array — Comma or space separated numbers, up to 40

1/43Start with 8 elements. Quick sort picks a pivot, partitions the range around it, then recurses on both sides (Lomuto partition, last element as pivot).

PivotComparing with pivotSwappedLess than pivotIn final position

PseudocodeLearn Quick Sort →

1quickSort(a, lo, hi):
2  if lo >= hi: return
3  pivot = a[hi]; i = lo
4  for j in lo .. hi-1:
5    if a[j] < pivot:
6      swap(a[i], a[j]); i = i + 1
7  swap(a[i], a[hi])   # pivot to final spot
8  quickSort(a, lo, i-1)
9  quickSort(a, i+1, hi)

Complexity

best O(n log n)

avg O(n log n)

worst O(n²)

space O(log n)

Speed

Pseudocode

1quickSort(a, lo, hi):
2  if lo >= hi: return
3  swap(a[randomIndex(lo, hi)], a[hi]); pivot = a[hi]; i = lo
4  for j from lo to hi - 1:
5    if a[j] < pivot: swap(a[i], a[j]); i += 1
6  swap(a[i], a[hi])
7  quickSort(a, lo, i - 1); quickSort(a, i + 1, hi)

Implementations

1import random
2 
3 
4def quick_sort(a: list[int]) -> None:
51 · Recursive sort with tail-loop on the larger side
6    def sort(lo: int, hi: int) -> None:
7        while lo < hi:
82 · Pick a random pivot and move it to the end
9            p = random.randint(lo, hi)
10            a[p], a[hi] = a[hi], a[p]
11            pivot = a[hi]
123 · Lomuto partition: a[lo..i) < pivot, a[i..j) >= pivot
13            i = lo
14            for j in range(lo, hi):
15                if a[j] < pivot:
16                    a[i], a[j] = a[j], a[i]
17                    i += 1
18            a[i], a[hi] = a[hi], a[i]  # pivot lands at its final index i
194 · Recurse on the smaller side, loop on the larger (O(log n) stack)
20            if i - lo < hi - i:
21                sort(lo, i - 1)
22                lo = i + 1
23            else:
24                sort(i + 1, hi)
25                hi = i - 1
26 
275 · Entry point
28    sort(0, len(a) - 1)

Walkthrough

random.randint(lo, hi) is inclusive on both ends, matching the closed range.
The pivot is swapped to a[hi] so range(lo, hi) scans everything else.
Tuple swaps advance the < pivot boundary i; the final swap places the pivot at i.
The while lo < hi loop plus recursion on the smaller side keeps depth at O(log n); Python's default recursion limit is 1000, so naive recursion would fail on large sorted inputs.
The nested function mutates a in place; rebinding lo/hi is fine because they are locals of sort.

Complexity (this implementation)

time O(n log n) average, O(n²) worst · space O(log n) stack

Pure-Python swaps are slow; list.sort() (C TimSort) is 50-100x faster. Use this to learn partitioning and quickselect.

Language notes

Python has no library quick sort; sorted is TimSort. heapq.nsmallest(k, a) covers most quickselect use cases.
The comprehension form quick_sort([x for x in a if x < p]) + [p] + ... is elegant but O(n) extra memory per level and not in place.
Recursion limit: sys.setrecursionlimit is a workaround; the tail loop above is the fix.

Common mistakes in this language

Using a[0] as the pivot — RecursionError on sorted input of a few thousand elements.
The list-comprehension version with <= on one side and > on the other is correct, but < and > alone drop duplicates.
Recursing on both sides instead of looping on the larger one.

Language differences that matter here

Library sorts are NOT quick sort in JS or Python: V8 and CPython use stable TimSort. C++ std::sort is introsort (quick sort + heap sort fallback + insertion sort), unstable and guaranteed O(n log n).
Stack depth: Python raises RecursionError at ~1000 frames and JS engines at ~10k; C++ segfaults on overflow. Recursing on the smaller side and looping on the larger keeps all four at O(log n).
Random numbers: C++ std::mt19937 + uniform_int_distribution (inclusive), Python random.randint (inclusive), JS Math.random() (needs the floor(random * (hi - lo + 1)) idiom).
Lomuto vs Hoare: Lomuto returns the pivot's final index (recurse on [lo, i-1] and [i+1, hi]); Hoare returns a split point (recurse on [lo, p] and [p+1, hi]) — mixing them up is the classic infinite loop, in any language.
JS [10, 2, 5].sort() sorts as strings; hand-written quick sort compares numerically.

Complexity

Best

O(n log n)

Average

O(n log n)

Worst

O(n²)

Space

O(log n)

Worst case with adversarial pivots; random or median-of-three pivots make it negligible; introsort bounds it at O(n log n). In-place, not stable, not adaptive.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

General in-memory sorting of primitives where stability is irrelevant — it is usually the fastest comparison sort in practice.
Memory-constrained sorting: O(log n) stack, no buffer.
As the engine behind Quickselect and partition-based problems.

Avoid it when

Stability is required — use Merge Sort / TimSort.
Hard worst-case guarantees on adversarial input with no randomization — use Heap Sort or introsort.
Linked lists (partitioning needs random access; merge sort is natural there).
Many duplicate keys without 3-way partitioning — 2-way Lomuto degrades to O(n²) on all-equal input.

Alternatives

Merge Sort Heap Sort TimSort Radix Sort

Compare: Merge Sort vs Quick Sort Compare: Quick Sort vs Heap Sort

Common mistakes

Always using a[lo] or a[hi] as the pivot — O(n²) on sorted or reverse-sorted input.
Recursing on both sides without the smaller-first trick, allowing O(n) stack depth.
Forgetting the final swap that places the pivot, or recursing on a range that includes the pivot (infinite recursion).
Hoare partition off-by-ones: the returned index is not the pivot's final position, so the recursion ranges differ from Lomuto's.
Expecting stability.

Interview patterns

Sort colors / Dutch national flag: 3-way partition in one pass.
Kth largest element via Quickselect.
Explain introsort and why std::sort never hits O(n²).
Partition an array so all negatives precede positives (unstable, O(n), O(1) space).

Interview questions on this