What is quick sort?
Quick sort picks one value from the array — the pivot — and rearranges everything else around it
in a single pass: smaller values slide left, larger values slide right, and the pivot lands exactly where
it belongs in the final sorted array. Then it repeats the same trick on the two smaller pieces on either
side, until every piece is down to one element.
- Pivot
- The value everything else gets compared against for one partition step
- Partition
- The single pass that slides smaller values left and larger values right of the pivot
- In-place
- Rearranging inside the original array — no second array to hold the result
Why quick sort at all?
Picture a line of people you need to sort by height. Instead of comparing every pair, you pick one person as a reference. Everyone shorter steps to their left, everyone taller steps to their right.
That reference person is now standing in their final position — nobody left of them is taller, nobody right of them is shorter. Repeat the same trick inside each smaller group and the whole line sorts itself.
Shorter than the reference moves left. Taller stays right. The reference settles last.
What actually happens inside partition?
Partition is the real engine of quick sort — everything else is just "do this again on a smaller piece." It comes down to picking a pivot, sweeping through once, and landing the pivot where it belongs.
Choose a pivot
Any element can be the pivot — the first one, the last one, a random one. The algorithm still works; only how well it splits the array depends on which one you pick.
First, last, or random — the pivot is just a starting reference value.
Scan once, swap as you go
j scans every element left to right. i marks the boundary of the "confirmed smaller
than pivot" zone. Whenever j finds something smaller than the pivot, it swaps into i's
slot and i steps forward — one pass, no nested loop.
i only advances — and swaps — when j finds a smaller value.
Recurse on both sides
Once the pivot lands in its final spot, everything left of it is smaller and everything right of it is larger. Run the exact same partition step inside each side, independently, until every piece is a single element.
Each side partitions on its own — quick sort never looks back across the boundary.
Two ways to choose a pivot
The partition logic never changes. What changes is which element becomes the pivot before that logic runs — and that single choice is what separates a fast sort from a slow one.
Fixed pivot
Always take the first element, or always the last. It's simple and cheap to compute — but it means the split quality depends entirely on where that fixed value happens to fall in the data.
Cheap to pick — but always exposed to whatever order the input arrives in.
function partition(arr: number[], lo: number, hi: number): number {
const pivot = arr[hi]; // always the last element
let i = lo;
for (let j = lo; j < hi; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[hi]] = [arr[hi], arr[i]]; // pivot into its final spot
return i; // pivot's sorted index
}
Random or median-of-three
Swap a randomly chosen element — or the median of the first, middle, and last — into the pivot slot before partitioning. It costs one extra step, but no single input order can reliably defeat it.
Once it's swapped to the end, partitioning proceeds exactly as before.
function partitionRandom(arr: number[], lo: number, hi: number): number {
const randomIndex = lo + Math.floor(Math.random() * (hi - lo + 1));
[arr[randomIndex], arr[hi]] = [arr[hi], arr[randomIndex]]; // pivot to the end
const pivot = arr[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[hi]] = [arr[hi], arr[i]];
return i;
}
Where it works — and where it breaks
Quick sort's average case is O(n log n) because a decent pivot splits the array into two roughly equal halves each time. Its worst case is O(n²) — and a bad, deterministic pivot choice makes that worst case easy to trigger by accident.
Balanced split, O(n log n)
A pivot near the middle of the value range splits the array into two pieces of similar size. Each
level of recursion cuts the remaining work roughly in half — log n levels deep.
Already-sorted input, O(n²)
Pick "always the last element" as the pivot on data that's already sorted, and the pivot is always the
largest remaining value. Every partition only removes one element — n levels deep instead of log n.