Quicksort Explained Visually — Step-by-Step with Code

Quicksort has a reputation problem: everyone knows it is fast, but the partitioning step — the part that actually does the work — is where most explanations go blurry. Two pointers, a pivot, some swaps that seem to happen for no reason. This guide fixes that by tracing every single comparison of a real partition, then building the rest of the algorithm on top of it.

The core idea is genuinely simple: pick one element (the pivot), rearrange the array so everything smaller sits to its left and everything larger to its right, and note that the pivot is now in its final sorted position — permanently. Then recursively do the same to the left chunk and the right chunk. No merge step, no copying back: the array sorts itself in place.

Partitioning, traced comparison by comparison

We will use the Lomuto scheme, the simplest common partition: the pivot is the last element, j scans the array left to right, and i marks the boundary of the "small elements" region — everything at index i or below is known to be ≤ pivot. Take the array [7, 2, 9, 4, 3, 8, 6, 5]. The pivot is 5, and i starts at −1 (empty small region).

1. j=0: compare 7 with pivot 5 → 7 > 5, do nothing → [7, 2, 9, 4, 3, 8, 6, 5]
2. j=1: compare 2 with 5 → 2 ≤ 5, grow the small region (i=0) and swap 2 into it → [2, 7, 9, 4, 3, 8, 6, 5]
3. j=2: compare 9 with 5 → 9 > 5, do nothing
4. j=3: compare 4 with 5 → 4 ≤ 5, i=1, swap 4 with 7 → [2, 4, 9, 7, 3, 8, 6, 5]
5. j=4: compare 3 with 5 → 3 ≤ 5, i=2, swap 3 with 9 → [2, 4, 3, 7, 9, 8, 6, 5]
6. j=5: compare 8 with 5 → 8 > 5, do nothing
7. j=6: compare 6 with 5 → 6 > 5, do nothing
8. Scan done: swap the pivot into position i+1=3 → [2, 4, 3, 5, 9, 8, 6, 7]

Look at the result. The pivot 5 sits at index 3 with [2, 4, 3] on its left (all smaller) and [9, 8, 6, 7] on its right (all larger). Neither side is sorted yet — and that is fine. The one guarantee partitioning gives us is that 5 will never move again. Seven comparisons, one pass, one element locked in place forever.

The recursion structure

Everything else is bookkeeping. Partition the whole array, then recurse on the left segment and the right segment; a segment of zero or one elements is already sorted, so the recursion bottoms out there. In our example, the next calls partition [2, 4, 3] and [9, 8, 6, 7] independently — they never interact again.

quicksort(array, low, high):
  if low >= high:
    return                       // 0 or 1 elements — done
  p = partition(array, low, high)
  quicksort(array, low, p - 1)   // left of pivot
  quicksort(array, p + 1, high)  // right of pivot

partition(array, low, high):     // Lomuto scheme
  pivot = array[high]
  i = low - 1
  for j from low to high - 1:
    if array[j] <= pivot:
      i = i + 1
      swap(array[i], array[j])
  swap(array[i + 1], array[high])
  return i + 1                   // pivot's final index

Note what is missing: there is no combine step. Once both recursive calls return, the segment is sorted — the partition already put every element on the correct side of the pivot, so the pieces fit together with zero extra work. Compare that with Merge Sort, where the split is trivial and *all* the work happens while merging back. The two algorithms are mirror images: Quicksort works on the way down, Merge Sort on the way up.

Pivot choice, and why the worst case is O(n²)

Quicksort is only fast when partitions are reasonably balanced. If the pivot lands near the middle, each level of recursion halves the problem, giving log n levels of O(n) partitioning work — O(n log n) total. But the pivot is just some element you picked; nothing forces it to be a good one.

Here is the classic failure. Run naive Quicksort (last element as pivot) on an already sorted array like [1, 2, 3, 4, 5]. The pivot 5 is the maximum, so partitioning splits into [1, 2, 3, 4] and an empty right side. Then pivot 4 does the same. Every level peels off exactly one element instead of half, so you get n levels doing n, n−1, n−2, ... comparisons — the same n(n−1)/2 sum that makes Bubble Sort quadratic. Sorted and reverse-sorted input, the most common "real" data shapes, are the worst case for the naive version.

• Random pivot — pick a random index and swap it to the end first. No fixed input is reliably bad; an adversary cannot construct a killer array without knowing your random choices.
• Median-of-three — take the median of the first, middle, and last elements. Cheap, and it handles sorted and reverse-sorted input gracefully.
• Introsort (what C++ std::sort does) — start with Quicksort, but if recursion depth exceeds ~2·log n, switch to heapsort. This caps the worst case at O(n log n) by construction.

With any of these, the expected running time is O(n log n) and the quadratic case becomes either vanishingly unlikely or outright impossible. The lesson is not "Quicksort is risky" — it is "never ship the textbook pivot".

Complexity at a glance

Why Quicksort usually beats Merge Sort in practice

On paper, Merge Sort looks safer: guaranteed O(n log n), no bad inputs. Yet well-implemented Quicksort is typically faster on real hardware, and the reasons are worth understanding because they apply far beyond sorting.

• It sorts in place. Merge Sort allocates an O(n) auxiliary buffer and copies every element through it at every level. Quicksort just swaps within the array — no allocation, no copy-back.
• Cache locality. Partitioning scans one contiguous region of the array sequentially, exactly the access pattern CPU caches and prefetchers are built for. Merging bounces between two source runs and a destination buffer, touching more memory per element.
• Small constants. The inner loop is a compare, an occasional swap, and a pointer increment — a few instructions that branch predictors handle well on random data.

Don't take this on faith — race them. The compare mode runs both algorithms on identical arrays side by side, so you can watch the step counts and see how differently they attack the same input.

When NOT to use Quicksort

• You need stability. Quicksort is not stable: partitioning swaps distant elements, so equal keys can end up reordered. If you sort records by name and then by city, the per-city name order is destroyed. Merge Sort (and Timsort) preserve it.
• Adversarial or untrusted input. With a predictable pivot, an attacker who knows your implementation can craft input that forces O(n²) — a real denial-of-service vector. Use a randomized pivot or introsort, or use Merge Sort/heapsort for a hard guarantee.
• Linked lists. Quicksort wants O(1) random access for swaps; Merge Sort handles lists naturally with pointer splicing and no extra array.
• Tiny arrays. Below roughly 10–20 elements, Insertion Sort wins on constants, which is why production Quicksorts hand small segments off to it.

Common misconceptions

• "The pivot must be the median." No — any element works; the pivot choice only affects balance, never correctness. The partition is correct regardless.
• "After one partition, each side is sorted." No — each side is merely on the correct side of the pivot. Only the pivot itself is in final position; the recursion sorts the rest.
• "Quicksort is always faster than Merge Sort." Only usually, on in-memory arrays, with a decent pivot. Stability requirements, linked structures, and worst-case guarantees all flip the answer.
• "O(n²) worst case means it is unsafe to use." With a randomized pivot the quadratic case requires astronomically bad luck, and introsort eliminates it entirely — which is why Quicksort variants power most standard library sorts for primitives.

Try it yourself

Partitioning clicks the moment you watch the small-elements boundary crawl forward and the pivot drop into the gap. Run Quicksort on a random array, then feed it a sorted one and watch the recursion tree degenerate into a stick. Then race it against Merge Sort and see the in-place advantage play out live.