Quick Sort Visualization

Quicksort is the algorithm that actually sorts most of the world’s data: variants of it power C’s qsort, C++’s std::sort, and countless runtime libraries. The idea: pick a pivot value, partition the array so everything smaller sits to its left and everything larger to its right, then recursively sort the two sides. After a partition, the pivot itself is in its final sorted position, permanently done. In the animation below, the purple bar is the current pivot; watch each one turn green the moment its partition finishes.

How it works

This implementation uses Lomuto partitioning: the last element of the range becomes the pivot, and a single left-to-right sweep compares every element against it, swapping the small ones into a growing “less than pivot” prefix. One final swap drops the pivot between the two groups, exactly where it belongs. Unlike merge sort, which does its work while recombining, quicksort does all its work before recursing, so you’ll see green bars appear scattered across the array, not in tidy waves.

On average, pivots land near the middle, the recursion is log n levels deep, and the total work is O(n log n) with excellent constant factors: tight loops, sequential access, no extra array. But the worst case is real: if every pivot is the smallest or largest element (which Lomuto hits on already sorted input), one side of each partition is empty and the recursion degenerates to O(n²) with O(n) stack depth. Production implementations dodge this with random or median-of-three pivots, and introsort bails out to heap sort if recursion gets too deep.

When interviewers ask about it

Quicksort is arguably the single most-asked sorting algorithm in interviews. Expect to write partition from memory, trace pivot positions by hand, and answer the classics: why is the worst case O(n²) and what input triggers it? How do you pick better pivots? Why isn’t it stable? (Long-range swaps can reorder equal elements.) The partition routine also stars in its own right: quickselect (finding the k-th smallest element in O(n) average time) and the Dutch national flag problem are both partition questions in disguise. If you can partition confidently, a whole family of interview problems falls open.

The challenge dedicates Day 26: Quicksort Algorithm to implementing and analyzing it, and Day 29: Comparison of Sorting Algorithms covers when to reach for quicksort versus merge sort or heapsort.

Complexity at a glance

The exact code you are watching

This is the real generator that drives the animation above, read from sort-algorithms.js at build time, so the code and the visualization can never drift apart. Each yield is one visual step.

 1function* quickSort(a) {
 2  yield* quickSortRange(a, 0, a.length - 1);
 3}
 4
 5function* quickSortRange(a, lo, hi) {
 6  if (lo > hi) {
 7    return;
 8  }
 9  if (lo === hi) {
10    yield { type: 'markSorted', i: lo };
11    return;
12  }
13  const p = yield* partition(a, lo, hi);
14  yield { type: 'markSorted', i: p };
15  yield* quickSortRange(a, lo, p - 1);
16  yield* quickSortRange(a, p + 1, hi);
17}
18
19// Lomuto partition: the last element is the pivot.
20function* partition(a, lo, hi) {
21  const pivot = a[hi];
22  yield { type: 'pivot', i: hi };
23  let i = lo;
24  for (let j = lo; j < hi; j += 1) {
25    yield { type: 'compare', i: j, j: hi };
26    if (a[j] < pivot) {
27      if (i !== j) {
28        const tmp = a[i];
29        a[i] = a[j];
30        a[j] = tmp;
31        yield { type: 'swap', i: i, j: j };
32      }
33      i += 1;
34    }
35  }
36  if (i !== hi) {
37    const tmp = a[i];
38    a[i] = a[hi];
39    a[hi] = tmp;
40    yield { type: 'swap', i: i, j: hi };
41  }
42  return i;
43}