Quick Sort: In-Place Partitioning and the Divide-and-Conquer Pattern
Quick Sort explained with the Lomuto in-place partition scheme — intuition, a worked walkthrough, JavaScript code, complexity analysis, and common mistakes.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Quick Sort is the sort that industrial-strength libraries reach for, and it earns that spot with one clever move: partitioning. Pick a pivot, shove everything smaller to its left and everything larger to its right, and that pivot is now sitting in its final sorted position — permanently. You never touch it again.
The magic is that partitioning solves nothing on its own but splits the array into two smaller problems you can sort the same way. Recurse on the left, recurse on the right, and a sequence of "put this one element where it belongs" steps compounds into a fully sorted array — with no extra scratch array, all in place.
The trap most people hit is the partition loop itself: two indices moving at different speeds, a swap that has to happen in exactly the right order, and a final pivot swap that's easy to get off by one. Get that loop right and the rest is just recursion.
The problem
Given an array of integers nums, sort it in ascending order. Quick Sort does this in place — it rearranges the array itself rather than building a new sorted copy.
Input: nums = [4, 2, 5, 1, 3]
Output: [1, 2, 3, 4, 5]Two properties define the algorithm we're implementing:
- In-place. Only O(log n) extra memory for the recursion stack — no auxiliary array per level.
- Not stable. Equal values can swap relative order during partitioning. If stability matters, merge sort is the tool.
The brute force baseline
Before Quick Sort, the simplest correct sort is a quadratic comparison sort like selection sort: walk the array, and for each position scan the rest to find the smallest remaining element.
function selectionSort(nums) {
for (let i = 0; i < nums.length; i++) {
let min = i;
for (let j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[min]) min = j;
}
[nums[i], nums[min]] = [nums[min], nums[i]];
}
return nums;
}This is correct but stubbornly slow. It compares nearly every pair of elements — n scans of up to n items each — for O(n²) comparisons, no matter what the input looks like. On a 100,000-element array that's ten billion comparisons. The wasted work is structural: selection sort re-scans the entire unsorted region on every single step, learning almost nothing it could carry forward.
The key insight: partition around a pivot
Quick Sort's reframe is to stop comparing every pair and instead do one cheap linear pass that answers a coarser question: for a chosen pivot, which elements are smaller and which are larger?
That single pass — the partition — accomplishes two things at once:
- The pivot lands in its final, correct position. Everything to its left is smaller; everything to its right is larger. It is done forever.
- The array is split into two independent subarrays. Neither half needs to interact with the other again, so you recurse on each.
Because each partition drops one element into place and halves the remaining work (on average), the comparisons collapse from O(n²) down to O(n log n). The pattern is divide and conquer: partition to divide, recurse to conquer.
The scheme below is Lomuto partitioning. It picks the last element as the pivot and uses a boundary index pos that marks the end of the "smaller than pivot" region as we scan.
The optimal solution
This is exactly the algorithm the Quick Sort visualizer steps through — a findPivotIndex helper doing the in-place partition, driven by a recursive quickSort.
function findPivotIndex(arr, startIndex, endIndex) {
const pivot = arr[endIndex];
let pos = startIndex - 1;
for (let i = startIndex; i < endIndex; i++) {
if (arr[i] < pivot) {
pos++;
[arr[i], arr[pos]] = [arr[pos], arr[i]];
}
}
[arr[pos + 1], arr[endIndex]] = [arr[endIndex], arr[pos + 1]];
return pos + 1;
}
function quickSort(arr, startIndex, endIndex) {
if (startIndex < endIndex) {
const pivotIndex = findPivotIndex(arr, startIndex, endIndex);
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
return arr;
}
}Read findPivotIndex as maintaining one invariant: everything in arr[startIndex..pos] is strictly less than the pivot. pos starts before the subarray (startIndex - 1) because that region is empty. Each time we find an element smaller than the pivot, we grow the smaller-region by one (pos++) and swap the small element into it. When the scan finishes, pos + 1 is the first slot not yet claimed by a smaller element — precisely where the pivot belongs. The final swap drops the pivot there and returns its resting index.
The base case is silent: when startIndex >= endIndex the subarray has zero or one element, so quickSort does nothing and unwinds. Correct partitioning plus a do-nothing base case is the whole algorithm.
Walkthrough: nums = [4, 2, 5, 1, 3]
Take the first partition call, findPivotIndex(arr, 0, 4). The pivot is arr[4] = 3, and pos starts at -1.
| i | arr[i] | arr[i] < 3? | pos after | swap | arr now |
|---|---|---|---|---|---|
| 0 | 4 | no | -1 | — | [4, 2, 5, 1, 3] |
| 1 | 2 | yes | 0 | arr[1]↔arr[0] | [2, 4, 5, 1, 3] |
| 2 | 5 | no | 0 | — | [2, 4, 5, 1, 3] |
| 3 | 1 | yes | 1 | arr[3]↔arr[1] | [2, 1, 5, 4, 3] |
Loop ends. Now place the pivot: swap arr[pos + 1] = arr[2] with arr[4], giving [2, 1, 3, 4, 5], and return pivotIndex = 2. The 3 is now permanently correct — everything left of it (2, 1) is smaller, everything right (4, 5) is larger.
Two recursive calls follow:
| Call | Subarray | Pivot | Result |
|---|---|---|---|
quickSort(arr, 0, 1) | [2, 1] | 1 | swaps to [1, 2, ...] → pivot index 0 |
quickSort(arr, 3, 4) | [4, 5] | 5 | already ordered → pivot index 4 |
Each of those spawns base cases that do nothing, and the array is fully sorted: [1, 2, 3, 4, 5]. Notice pos only advanced on the two elements smaller than the pivot — the boundary index is doing the bookkeeping selection sort couldn't.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Selection sort | O(n²) | O(1) | full rescan of the unsorted region every step |
| Quick Sort (average) | O(n log n) | O(log n) | ~log n partition levels, each a linear O(n) pass; stack = recursion depth |
| Quick Sort (worst) | O(n²) | O(n) | a pivot that never splits — one side always empty — gives n levels |
The average case assumes each partition roughly halves the array, giving log n levels of O(n) work. The worst case is real: on an already-sorted input, the last-element pivot is always the maximum, so every partition peels off just one element and recursion goes n deep. Random or median-of-three pivot selection makes that worst case astronomically unlikely.
Common mistakes
- Initializing
postostartIndexinstead ofstartIndex - 1. The smaller-region is empty at the start, so its boundary must sit one slot before the subarray. Starting atstartIndexplaces the first small element one position too far right. - Using
<=instead of<in the comparison. With<, elements equal to the pivot stay in the right partition, which keeps the loop bounds honest. Switching to<=still sorts but shifts equal keys and muddies the invariant. - Forgetting the final pivot swap. The scan alone leaves the pivot stranded at
endIndex. Without thearr[pos + 1] ↔ arr[endIndex]swap, the returned index doesn't hold the pivot and the recursion sorts the wrong ranges. - Off-by-one in the recursive ranges. It must be
pivotIndex - 1andpivotIndex + 1. IncludingpivotIndexin either half re-sorts an already-placed element and can loop forever on duplicates. - Assuming stability. Partitioning swaps distant elements, so equal keys can reorder. Never reach for Quick Sort when the original order of equal items must be preserved.
Where this pattern shows up next
Quick Sort is a comparison sort — its O(n log n) is the ceiling for comparing pairs. The next leap is to sort without comparing at all, exploiting the structure of the keys:
- Counting Sort — tally each value and rebuild the array from counts, for O(n + k) time on small integer ranges.
- Counting Sort - Stable - Logic — why right-to-left placement with prefix-sum end-pointers keeps equal keys in order, the stability Quick Sort lacks.
- Radix Sort — apply stable counting sort digit by digit to sort large integers in linear time.
- Bucket Sort — scatter values into range-based buckets, sort each, then concatenate.
You can also step through Quick Sort interactively to watch the partition boundary crawl forward and each pivot snap into place.
FAQ
What is the time complexity of Quick Sort?
O(n log n) on average and O(n²) in the worst case. The average case comes from partitions that roughly halve the array, producing about log n levels of recursion with a linear O(n) pass at each level. The worst case happens when the pivot never splits the data — for example, a last-element pivot on an already-sorted array — forcing n levels of one-element partitions. Randomized or median-of-three pivots make the worst case practically unreachable.
Why is Quick Sort not stable?
Because partitioning swaps elements that can be far apart, two equal values can end up in the opposite relative order they started in. Stability requires that equal keys never cross each other, and the Lomuto swap makes no such guarantee. When you need equal items to keep their original order — sorting records by one field after another, for instance — use merge sort, which is stable, instead.
How does Lomuto partitioning actually work?
It picks the last element as the pivot and keeps a boundary index pos marking the end of the "smaller than pivot" region, which starts empty at startIndex - 1. A single left-to-right scan checks each element: whenever one is smaller than the pivot, pos advances and that element is swapped into the smaller region. After the scan, one final swap moves the pivot to pos + 1, its correct sorted slot, and that index is returned so recursion can sort the two halves around it.
Does Quick Sort use extra memory?
Only for the recursion stack, not for the data. Quick Sort rearranges the array in place through swaps, so it needs no auxiliary array. The stack depth is O(log n) on average and O(n) in the worst case; sorting the larger partition via a loop and recursing only on the smaller one (tail-call elimination) bounds the stack at O(log n) even in the worst case.
When should I use Quick Sort over merge sort?
Reach for Quick Sort when memory is tight and average-case speed matters more than worst-case guarantees. It sorts in place with excellent cache locality, which usually makes it faster in practice than merge sort despite the same average complexity. Choose merge sort instead when you need guaranteed O(n log n) regardless of input, or when stability is required — merge sort delivers both at the cost of O(n) extra space.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.