Quick Sort — Sorting

Overview

What this concept solves

Quicksort is the in-memory speed champion — when you control the pivot. Pick any element as the pivot. Partition the rest: everything smaller goes left of it, everything larger goes right. Now the pivot is in its final sorted position, and you recurse on the two sides. Each pivot eats one element off the problem; partitioning is linear. Average depth is log n. Average work is O(n log n) with the tightest constants of any comparison sort.

The win is two things at once: it's in-place (no buffer the size of the input like merge sort needs) and it's cache-friendly (the partition step reads and writes sequentially). On random data, quicksort beats merge sort by roughly 2× in practice — same algorithmic class but better constants.

The catch is the worst case is O(n²), hit when every pivot lands at one end of its range — exactly what happens if you always pick the last element as pivot and the input is already sorted. Real implementations dodge this with randomised or median-of-three pivot selection, plus an introsort fallback (switch to heap sort if recursion gets too deep). Done right, quicksort is the fastest practical comparison sort. Done naively, it's a bug waiting for adversarial input.

Mechanics

How it works

Partition (Lomuto's scheme)

Choose pivot = a[hi] (the rightmost element of the current range).
Keep a boundary i just left of the smaller-than-pivot region.
Scan j from lo to hi-1. If a[j] < pivot, advance i and swap a[i] with a[j].
After the scan, swap a[i+1] with the pivot at a[hi]. The pivot now sits at its final sorted position i+1.
Return that position — everything left of it is smaller, everything right is larger.

The recursion

Call quicksort(lo, hi). If lo >= hi, return — the range is sorted.
Partition. Let p be the pivot's final position.
Recurse on quicksort(lo, p-1).
Recurse on quicksort(p+1, hi).
Bottom out when ranges shrink to length 0 or 1.

Why the average case is O(n log n)

If the pivot lands near the middle of its range, both halves are ~n/2 and the recursion is log n deep. Each level still partitions a total of n elements. n × log n. The 'near the middle' part holds on expectation for random pivots — even badly-balanced splits average out as long as the pivot isn't pathologically picked.

The O(n²) trap and how production sorts dodge it

Always picking a[hi] on a sorted input means the pivot is always the max of its range, so the left half is everything-but-one and the right half is empty. Recursion is n deep, work per level is n, total n². Fix: pick the pivot randomly, or use median-of-three (median of a[lo], a[mid], a[hi]). Both make adversarial inputs astronomically unlikely. Real-world sorts go further with introsort: track recursion depth, fall back to heap sort if it exceeds 2 log n.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Quick Sort

About this simulation

A pivot (purple) is chosen, the rest of the range is partitioned into smaller-than-pivot and bigger-than-pivot, and the pivot lands in its final sorted position. Press Play to watch the recursion unfold across the whole array, Step / Back to walk each compare-and-swap, Shuffle for a new list.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Play through one full sort

Press Play. Watch the purple pivot get chosen at the right edge of the range. Then watch the orange scanner walk left-to-right, occasionally swapping (red flash) to move smaller-than-pivot values into the left group. At the end of the scan the pivot snaps into its final sorted slot (green) and the recursion divides the range into two smaller ranges.

try 02

Count the partitions

The Pivots set counter increments once per partition — that's exactly the number of recursive calls. For 8 elements that's typically 6–8 calls. Each call's partition does linear work on its range; the sum across all levels is the n log n total.

try 03

Step into one partition

Use Step to enter a partition. Each tick of Comparisons is one a[j] < pivot? check; each tick of Swaps is one move into the smaller-than-pivot group. After the scan completes, watch the final pivot swap — that's the moment the pivot lands at its sorted home.

try 04

Shuffle until you see a bad pivot

Press Shuffle repeatedly. Look for inputs where the right-most element is unusually small or large — that's when the partition produces a lopsided split (one big side, one tiny side) and the recursion gets deep. That's quicksort's worst-case path in miniature. Real implementations defend with randomised pivot selection (this prototype uses fixed a[hi] for clarity).

In practice

When to use it — and what you give up

When it's the right tool

General-purpose in-memory sorting of random data — fastest practical comparison sort.
Memory-constrained environments — O(log n) recursion stack, no buffer.
You can randomise the pivot — adversarial inputs become a non-issue.
You can apply introsort — guarantees O(n log n) worst case by escape-hatch into heap sort.
Cache locality matters — partition is a sequential scan, very friendly to modern memory hierarchies.

When to reach for something else

You need stability — quicksort is not stable; use Timsort or merge sort.
You can't trust the input distribution and can't afford the O(n²) worst case — use heap sort or merge sort.
You're sorting a linked list — quicksort needs random access; use merge sort.
Data is already nearly sorted — Timsort exploits existing runs; quicksort gets its worst case.
You're sorting integers with a known small range — counting or radix sort beats every comparison sort.

Pros

Fastest in-memory comparison sort on random data — beats merge sort by ~2× in practice.
In-place — only O(log n) stack space for the recursion.
Cache-friendly — sequential reads and writes during partitioning.
Tail-recursion elimination — modern implementations turn the second recursive call into a loop, cutting stack depth.
Easy to make hostile-input-resistant with randomised or median-of-three pivot selection.

Cons

O(n²) worst case if pivot selection goes bad — must defend with randomisation or introsort fallback.
Not stable — equal elements can be reordered during partitioning.
Recursion can blow the stack on adversarial inputs without depth limits.
Slower on nearly-sorted data than Timsort — gets its worst case exactly when the data is best-prepared.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

quick-sort.ts

// Quicksort with Lomuto partition.
// Average O(n log n) in-place; worst O(n²) on bad pivots.
// Production code should randomise the pivot to dodge worst-case inputs.
function quickSort<T>(a: T[], lo = 0, hi = a.length - 1): T[] {
  if (lo >= hi) return a;
  const p = partition(a, lo, hi);
  quickSort(a, lo, p - 1);
  quickSort(a, p + 1, hi);
  return a;
}

function partition<T>(a: T[], lo: number, hi: number): number {
  // For a hostile-input-resistant version, swap a[hi] with a[lo + random(hi-lo+1)] here.
  const pivot = a[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (a[j] < pivot) {
      i++;
      [a[i], a[j]] = [a[j], a[i]];
    }
  }
  [a[i + 1], a[hi]] = [a[hi], a[i + 1]];
  return i + 1;
}

// Example
quickSort([10, 7, 8, 9, 1, 5]);
// → [1, 5, 7, 8, 9, 10]

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

What's the worst-case time complexity of quicksort with the rightmost element as pivot, on already-sorted input?

question 02 / 03

Which production-grade quicksort variant gives an O(n log n) worst-case guarantee?

question 03 / 03

Quicksort isn't stable. What does that mean in practice for sorting records by multiple keys?

0/3 answered