Quicksort

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Quicksort

Loading interactive demo…

Quicksort picks a pivot, splits the array around it in place, then sorts each side the same way. Take the tour, or press and explore. Legend:

The panel beside the stage is the real Quicksort class from the published library executing in your browser, with the current line highlighted.

The pivot of the current range - always the brightest bar. When its partition finishes it swaps into its final slot and never moves again.
The sweeping cursor compared against the pivot, or the two slots being swapped. The bracket points at the pair involved in the current step.
Every bar, once the whole array is sorted.

Balanced pivots give O(n log n); a sorted input with last-element pivots degrades to O(n²). Drag the bars into sorted order, press , and watch the comparison count blow up.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Each partition compares every element of its range with the pivot, so the total cost is the sum of the range sizes. Balanced pivots halve the range every level:

T(n) = 2\,T\!\left(\tfrac{n}{2}\right) + n - 1 = O(n \log n)

and a random pivot gets close to that on average, about $2n \ln n \approx 1.39\, n \log_2 n$ comparisons. But the last-element pivot used here has a famous blind spot: on an already sorted array every partition splits $n$ into $n-1$ and $0$ , so the ranges shrink by one and the sum is

(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2} = O(n^2).

Drag the bars into sorted order and watch the comparison counter - that is why production quicksorts pick pivots more carefully (median-of-three, random) and cap the recursion depth.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

This is the Lomuto partition scheme: one boundary index, one left-to-right sweep - the easiest scheme to reason about. Hoare's original two-pointer scheme does fewer swaps but is trickier to get right.
boundary always points at the first slot of the "bigger than pivot" region; ≤ sends equal elements left, so the recursion always excludes the pivot and cannot loop forever on duplicates.
The pivot placement swap runs even when the pivot is already in place - a deliberate simplification: one unconditional line instead of a branch that saves almost nothing.
sort copies the input once ([...input]) and then partitions in place - the recursion shares one array, passing only the lo/hi range boundaries.

Tony Hoare invented quicksort in 1959 as a young visiting student in Moscow, trying to sort Russian words before looking them up on a dictionary tape for a machine-translation project. The recursive partition idea needed a language that could express recursion - so it was published in 1961, right after ALGOL 60 made that possible. It remains the canonical divide-and-conquer algorithm and the backbone of most standard-library sorts.

1959Tony Hoare - Devises the partition scheme while working on machine translation in Moscow, sorting words to match a dictionary tape.source
1961Tony Hoare - Publishes Algorithm 64: Quicksort in Communications of the ACM - a few lines of ALGOL exercising the brand-new idea of recursion.source
1975Robert Sedgewick - PhD thesis gives the definitive analysis and the practical refinements - median-of-three pivots, small-run cutoffs - used ever since.source
1997David Musser - Introsort caps quicksort's recursion depth and falls back to heapsort, taming the worst case for C++ standard libraries.source
2009Vladimir Yaroslavskiy - Dual-pivot quicksort beats the classic scheme in practice and becomes Java's default sort for primitive arrays.source

Used today

Standard-library sorts - C's qsort, C++'s std::sort (as introsort), and Java's primitive sort (dual-pivot) are all quicksort variants.
Quickselect - Partition once and recurse into one side to find the k-th smallest element in expected linear time.
In-place workhorse - Sorts with O(log n) extra space and cache-friendly sequential sweeps - why it beats mergesort in memory-tight settings.

n16

comparisons: 0
swaps: 0

quicksort.ts

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Quicksort with Lomuto partitioning: pick the last element of the * range as the pivot, sweep a cursor across the range moving smaller * elements to the low side, drop the pivot after them, then recurse on * both sides. * * Time: O(n log n) expected, O(n²) worst case. Space: O(log n) stack * expected, O(n) worst case: on sorted input the last-element pivot * splits off one element per call, so the recursion goes n deep. */export class Quicksort implements SortAlgorithm {  readonly name = "quicksort";  constructor(private readonly tracer?: Tracer) {}  sort(input: readonly number[]): number[] {    const a = [...input];    const array = [...input];    this.sortRange(a, 0, a.length - 1);    this.sortRange(array, 0, array.length - 1);    return a;    return array;  }  private sortRange(a: number[], lo: number, hi: number): void {  private sortRange(array: number[], low: number, high: number): void {    if (lo >= hi) return;    if (low >= high) return;    const p = this.partition(a, lo, hi);    const pivotIndex = this.partition(array, low, high);    this.sortRange(a, lo, p - 1);    this.sortRange(array, low, pivotIndex - 1);    this.sortRange(a, p + 1, hi);    this.sortRange(array, pivotIndex + 1, high);  }  private partition(a: number[], lo: number, hi: number): number {  private partition(array: number[], low: number, high: number): number {    const pivot = a[hi]!;    const pivot = array[high]!;    // ▸ take the last element of the range as the pivot    this.tracer?.emit("select-pivot", { lo, hi, pivot, array: [...a] });    this.tracer?.emit("select-pivot", { low, high, pivot, array: [...array] });    let boundary = lo; // first slot holding an element larger than the pivot    let boundary = low; // first slot holding an element larger than the pivot    for (let j = lo; j < hi; j++) {    for (let cursor = low; cursor < high; cursor++) {      // ▸ is this element within the pivot's low side      this.tracer?.emit("compare", { lo, hi, j, boundary, pivot, array: [...a] });      this.tracer?.emit("compare", { low, high, cursor, boundary, pivot, array: [...array] });      if (a[j]! <= pivot) {      if (array[cursor]! <= pivot) {        if (j !== boundary) {        if (cursor !== boundary) {          // ▸ move it into the low side          this.tracer?.emit("swap", { lo, hi, i: boundary, j, array: [...a] });          this.tracer?.emit("swap", { low, high, i: boundary, cursor, array: [...array] });          const held = a[boundary]!;          const held = array[boundary]!;          a[boundary] = a[j]!;          array[boundary] = array[cursor]!;          a[j] = held;          array[cursor] = held;        }        boundary++;      }    }    // ▸ drop the pivot right after the low side    this.tracer?.emit("place-pivot", { lo, hi, from: hi, to: boundary, array: [...a] });    this.tracer?.emit("place-pivot", { low, high, from: high, to: boundary, array: [...array] });    const held = a[boundary]!;    const held = array[boundary]!;    a[boundary] = a[hi]!;    array[boundary] = array[high]!;    a[hi] = held;    array[high] = held;    return boundary;  }}

The array before sorting. Quicksort will partition it around pivots.

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Quicksort with Lomuto partitioning: pick the last element of the * range as the pivot, sweep a cursor across the range moving smaller * elements to the low side, drop the pivot after them, then recurse on * both sides. * * Time: O(n log n) expected, O(n²) worst case. Space: O(log n) stack * expected, O(n) worst case: on sorted input the last-element pivot * splits off one element per call, so the recursion goes n deep. */export class Quicksort implements SortAlgorithm { readonly name = "quicksort"; constructor(private readonly tracer?: Tracer) {} sort(input: readonly number[]): number[] { const a = [...input]; const array = [...input]; this.sortRange(a, 0, a.length - 1); this.sortRange(array, 0, array.length - 1); return a; return array; } private sortRange(a: number[], lo: number, hi: number): void { private sortRange(array: number[], low: number, high: number): void { if (lo >= hi) return; if (low >= high) return; const p = this.partition(a, lo, hi); const pivotIndex = this.partition(array, low, high); this.sortRange(a, lo, p - 1); this.sortRange(array, low, pivotIndex - 1); this.sortRange(a, p + 1, hi); this.sortRange(array, pivotIndex + 1, high); } private partition(a: number[], lo: number, hi: number): number { private partition(array: number[], low: number, high: number): number { const pivot = a[hi]!; const pivot = array[high]!; // ▸ take the last element of the range as the pivot this.tracer?.emit("select-pivot", { lo, hi, pivot, array: [...a] }); this.tracer?.emit("select-pivot", { low, high, pivot, array: [...array] }); let boundary = lo; // first slot holding an element larger than the pivot let boundary = low; // first slot holding an element larger than the pivot for (let j = lo; j < hi; j++) { for (let cursor = low; cursor < high; cursor++) { // ▸ is this element within the pivot's low side this.tracer?.emit("compare", { lo, hi, j, boundary, pivot, array: [...a] }); this.tracer?.emit("compare", { low, high, cursor, boundary, pivot, array: [...array] }); if (a[j]! <= pivot) { if (array[cursor]! <= pivot) { if (j !== boundary) { if (cursor !== boundary) { // ▸ move it into the low side this.tracer?.emit("swap", { lo, hi, i: boundary, j, array: [...a] }); this.tracer?.emit("swap", { low, high, i: boundary, cursor, array: [...array] }); const held = a[boundary]!; const held = array[boundary]!; a[boundary] = a[j]!; array[boundary] = array[cursor]!; a[j] = held; array[cursor] = held; } boundary++; } } // ▸ drop the pivot right after the low side this.tracer?.emit("place-pivot", { lo, hi, from: hi, to: boundary, array: [...a] }); this.tracer?.emit("place-pivot", { low, high, from: high, to: boundary, array: [...array] }); const held = a[boundary]!; const held = array[boundary]!; a[boundary] = a[hi]!; array[boundary] = array[high]!; a[hi] = held; array[high] = held; return boundary; }}