Quick Sort Visualizer

Quick sort is the fastest general-purpose comparison sort in practice, and it has a worst case of O(n²). Both statements are true, and the tension between them is the most interesting thing in elementary algorithms — an entire body of engineering exists purely to make the bad case unreachable while keeping the good case fast.

The mechanism is one idea: pick an element, called the pivot, and rearrange the array so everything smaller sits to its left and everything larger to its right. The pivot is now in its final position, and you have two smaller problems that can be solved the same way. No merging is needed, because the partitioning has already put the pieces in the right relationship to each other.

What is quick sort?

Quick sort is a divide-and-conquer, in-place, comparison-based sort. Unlike merge sort, which does trivial splitting and all its work in the combine step, quick sort does all its work in the divide step and needs no combine step at all. Once both sides of a pivot are sorted, the array is sorted — there is nothing left to do.

The partitioning is what makes it fast. A single pass over a sub-array of length m rearranges it in place with m−1 comparisons, using sequential memory access that modern CPU prefetchers handle beautifully. Merge sort's copying and quick sort's partitioning both cost Θ(n) per level, but quick sort's constant is smaller and its cache behaviour is better.

The visualiser uses Lomuto partitioning, which takes the last element as pivot and maintains a boundary index i marking the end of the 'smaller than pivot' region. It is the easiest scheme to read and to reason about. Production implementations usually use Hoare partitioning, which is about three times fewer swaps but harder to get right.

Why it works

The invariant during partitioning is: everything in A[lo..i] is ≤ the pivot, and everything in A[i+1..j-1] is > the pivot. The loop maintains it by extending the second region for free when A[j] > pivot, and by swapping A[j] into the first region when it is not.

When the scan finishes, swapping the pivot into position i+1 places it with all smaller elements to its left and all larger to its right. The pivot is now in its final sorted position — this is the key claim, and it is why no combine step is needed. Its position cannot change, because nothing in the left partition will ever exceed it and nothing in the right will ever fall below it.

Recursing on both sides then sorts them internally, and the concatenation of a sorted left partition, the pivot, and a sorted right partition is a sorted array. Induction on partition size completes the proof.

Step-by-step walkthrough

Partition [10, 80, 30, 90, 40, 50, 70] with the last element, 70, as pivot. The boundary i starts just before the array.

1. j = 0: 10 ≤ 70, so advance i to 0 and swap with itself. [10, 80, 30, 90, 40, 50, 70].
2. j = 1: 80 > 70, so do nothing — it stays in the 'greater' region.
3. j = 2: 30 ≤ 70, so advance i to 1 and swap 30 with 80: [10, 30, 80, 90, 40, 50, 70].
4. j = 3: 90 > 70, nothing happens.
5. j = 4: 40 ≤ 70, advance i to 2 and swap 40 with 80: [10, 30, 40, 90, 80, 50, 70].
6. j = 5: 50 ≤ 70, advance i to 3 and swap 50 with 90: [10, 30, 40, 50, 80, 90, 70].
7. Scan ends. Swap the pivot into position i+1 = 4: [10, 30, 40, 50, 70, 90, 80]. 70 is now final, with [10, 30, 40, 50] left and [90, 80] right to sort recursively.

Pivot selection is the whole engineering problem

Quick sort's complexity is decided entirely by how balanced the partitions are, and that is decided entirely by the pivot. This is why pivot selection, not partitioning, is where all the practical work has gone.

Last or first element is the textbook choice and the worst one. It makes already-sorted and reverse-sorted input — two of the most common shapes real data takes — trigger the O(n²) worst case. A sorted array is not an adversarial input; it is Tuesday.

Random pivot makes the worst case a matter of luck rather than input shape. The expected time is O(n log n) for any input, and the probability of anything near quadratic behaviour becomes vanishingly small. It costs one random number per partition.

Median-of-three takes the median of the first, middle and last elements. It is cheap, deterministic, and handles sorted and reverse-sorted input well, which is why it appears in so many real implementations. It can still be defeated by a deliberately constructed input.

Introsort, the approach in the C++ standard library, is the honest engineering answer: run quick sort with median-of-three, track the recursion depth, and when it exceeds about 2·log₂n — which only happens if partitioning is going badly — switch that branch to heap sort. You get quick sort's average speed with a hard O(n log n) worst-case guarantee.

How the animation above works

The white bar is the pivot; the violet band is the sub-array currently being partitioned. Watch a single partition pass and you will see the boundary creep right as small values are swapped into it, then the pivot swap at the end that plants a mint bar — a final position — in the middle of the array.

For the lesson that matters most, set the arrangement to reversed or sorted and watch what happens. Because this implementation uses last-element pivoting, the partitions become maximally unbalanced and the comparison count jumps towards n²/2. Then switch back to random and watch it drop by an order of magnitude. Same code, same array size, wildly different cost — decided entirely by the pivot's relationship to the data.

Time complexity

Best case O(n log n). A pivot that lands near the median halves the problem each time, giving log₂n levels of Θ(n) work.

Average case O(n log n). Averaged over all input permutations, the expected comparison count is about 1.39·n·log₂n. That 39% overhead against the theoretical minimum is more than repaid by the small constant factor and cache behaviour, which is why quick sort typically beats merge sort in wall-clock time despite doing more comparisons.

Worst case O(n²). Maximally unbalanced partitions, which last-element pivoting produces on sorted input. Random or median-of-three pivoting reduces this to a probability so small it can be ignored; introsort eliminates it outright.

One subtlety worth knowing: arrays with many duplicate values degrade Lomuto partitioning badly, because every element equal to the pivot goes into the same partition. Three-way partitioning — splitting into less-than, equal-to and greater-than — fixes this and turns an array of all-identical values from O(n²) into O(n).

Space and stability

Quick sort partitions in place, so it needs no auxiliary array. Its space cost is the recursion stack: O(log n) when partitions are balanced, O(n) in the degenerate case. Recursing on the smaller partition first and looping on the larger — tail-call elimination by hand — bounds the stack at O(log n) regardless of how badly the pivots behave.

It is not stable. Partitioning swaps elements across long distances, so two equal elements can be reordered by a swap that involves neither of them. Making it stable requires O(n) extra space, at which point merge sort is the better tool.

This is exactly why C++'s std::sort (introsort, unstable) and std::stable_sort (merge-based) are separate functions, and why Java uses quick sort for primitive arrays but Timsort for object arrays: primitives have no identity beyond their value, so stability is meaningless for them.

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Quick Sort in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * Quick sort with Lomuto partitioning and a randomised pivot.
 *
 * The random swap before partitioning is not decoration: with a fixed
 * last-element pivot, an already-sorted array is the O(n^2) worst case.
 */
function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;

  const p = partition(arr, lo, hi);
  quickSort(arr, lo, p - 1);
  quickSort(arr, p + 1, hi);
  return arr;
}

function partition(arr, lo, hi) {
  // Randomise the pivot, then move it to the end so the scan below is simple.
  const random = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[random], arr[hi]] = [arr[hi], arr[random]];

  const pivot = arr[hi];
  let i = lo - 1;

  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

console.log(quickSort([10, 80, 30, 90, 40, 50, 70]));

Advantages and disadvantages

Real-world applications

• The default std::sort in C++ — technically introsort, which is quick sort with a heap sort fallback when recursion goes too deep.
• Java's Arrays.sort() for primitive types, which uses dual-pivot quick sort.
• Quickselect, the same partitioning applied to find medians and k-th order statistics in expected linear time.
• Database query engines sorting in-memory result sets where stability is not required.
• Any latency-tolerant, memory-constrained sorting task where the O(n) buffer merge sort needs is unaffordable.
• The Dutch national flag partitioning inside it is a standard technique for three-way grouping problems far beyond sorting.

Interview questions

The questions that actually get asked about Quick Sort, with the answers an interviewer is listening for.

1. Q1. What is quick sort's worst case and when does it happen?

   O(n²), which occurs when every partition is maximally unbalanced — one side holds n−1 elements and the other none. With last-element pivoting this happens on already-sorted and reverse-sorted arrays, which are extremely common in practice. Randomised or median-of-three pivoting makes it improbable rather than input-dependent; introsort eliminates it by switching to heap sort past a depth limit.

2. Q2. Explain the difference between Lomuto and Hoare partitioning.

   Lomuto uses a single forward scan with a boundary index and swaps every element that is ≤ the pivot; it is easier to understand and to prove correct. Hoare runs two pointers inwards from both ends and swaps only when both are on the wrong side, performing roughly three times fewer swaps. Hoare is faster and is what production code uses, but it does not place the pivot in its final position, so the recursion bounds differ and it is easier to get wrong.

3. Q3. How would you make quick sort handle arrays with many duplicates efficiently?

   Use three-way partitioning — the Dutch national flag scheme — which splits into less-than, equal-to and greater-than regions. The equal band is already in its final position, so the recursion skips it entirely. An array where every element is identical goes from O(n²) with Lomuto to O(n) with three-way partitioning.

4. Q4. Why is quick sort usually faster than merge sort despite the worse worst case?

   Three reasons. It sorts in place, so there is no O(n) buffer to allocate or copy through. Its partition scan is sequential, so cache behaviour is excellent. And its inner loop is very tight — a comparison, an increment and an occasional swap. Merge sort does more copying and strides across memory more, so despite doing slightly fewer comparisons it usually loses on wall-clock time.

5. Q5. How do you bound quick sort's stack usage?

   Always recurse into the smaller partition and loop on the larger one. Because the smaller partition is at most half the current range, the recursion depth is bounded by log₂n even when partitioning is pathological — the unbalanced case becomes iteration instead of recursion, which costs no stack at all.

Common mistakes

• Always choosing the first or last element as pivot, which makes already-sorted input the O(n²) worst case — the single most common quick sort bug in production.
• Recursing on (lo, p) instead of (lo, p - 1), which re-includes the pivot and causes infinite recursion.
• Using < instead of <= in the Lomuto comparison, which sends elements equal to the pivot to the wrong side and degrades badly on duplicate-heavy arrays.
• Forgetting the final swap that moves the pivot into position i+1 — the partition looks nearly right and the output is subtly wrong.
• Recursing into both partitions without the smaller-first trick, which risks stack overflow on adversarial input.
• Assuming quick sort is stable and using it to sort records by a secondary key.
• Computing the midpoint for median-of-three as (lo + hi) / 2, which overflows in fixed-width integer languages.

Optimisation tips

• Randomise the pivot, or use median-of-three. This is not an optimisation so much as a correctness requirement for real data.
• Switch to insertion sort for partitions below roughly sixteen elements — or leave them unsorted and run one insertion sort pass over the whole nearly-sorted array at the end.
• Use three-way partitioning when duplicates are likely, which is most real datasets with categorical fields.
• Recurse into the smaller partition and iterate on the larger, bounding stack depth at O(log n).
• Add a depth limit and fall back to heap sort when it is exceeded — that is introsort, and it buys a hard O(n log n) guarantee for almost no cost.
• Consider dual-pivot quick sort, which partitions into three regions around two pivots and is measurably faster on primitives; it is what Java uses for int[].

Summary

Quick sort partitions the array around a pivot so smaller elements land left and larger land right, placing the pivot in its final position, then recurses into both sides. No combine step is needed. It sorts in place with O(log n) stack and averages O(n log n) with a small constant factor, which makes it the fastest comparison sort in practice.

Its weakness is that performance is decided by pivot quality, and the textbook last-element pivot turns sorted input — an extremely common case — into the O(n²) worst case. Randomise the pivot or use median-of-three, add three-way partitioning if duplicates are likely, and cap the recursion depth with a heap sort fallback. Do those things and you have introsort, which is what your standard library is already running.

Frequently asked questions

Related algorithms

• Merge Sort

  Split the array down to single elements, then merge sorted halves back together.

  O(n log n)Intermediate

• Heap Sort

  Build a max-heap, then repeatedly pull the root to the end of the array.

  O(n log n)Advanced

• Bubble Sort

  Repeatedly swap adjacent pairs until the largest values have bubbled to the end.

  O(n²)Beginner