Module P-10 — Sorting III: Quick Sort and Partitioning
What this module covers: Quick sort is divide-and-conquer with a different split than Module P-9's merge sort: instead of splitting the array in half blindly and merging afterward, it partitions the array around a chosen value so that combining the two sides afterward requires no work at all. This module covers partitioning (the same three-pointer shape as Module F-8's Sort Colors), pivot selection, and the honest trade-off — average-case O(n log n) that can degrade to O(n²) on the wrong input.
Partitioning: Do the Combining Work First
Quick sort picks a pivot value, then rearranges the array so that everything smaller than the pivot ends up to its left, and everything larger ends up to its right — with the pivot itself landing in its final, correct sorted position. Once that's done, the two sides can be sorted independently and recursively, with no merge step needed afterward, because the partition already guaranteed every element on the left belongs before every element on the right.
typescript
This is the identical shape as Module F-8's sortColors (Dutch national flag): a boundary pointer (i) tracks "confirmed smaller," a scanning pointer (j) walks forward once, and elements are swapped into place as the scan proceeds — one pass, O(n), no auxiliary array. The pivot ends up exactly at index i + 1, with every smaller element to its left and every larger element to its right, guaranteed.
Quick Sort: Partition, Then Recurse on Each Side
typescript
Compare this directly to Module P-9's mergeSort: merge sort splits blindly (down the middle) and does real, O(n) work after the recursive calls return (the merge step); quick sort does its O(n) work before recursing (the partition), and needs nothing at all afterward — the two sorted halves, once partitioned correctly, are already a fully sorted whole array. This is why quick sort sorts in place: no second array is ever allocated to hold merged results — every operation happens by swapping elements within the original array.
Why Pivot Choice Determines Everything
If partitioning always split the array into two genuinely equal halves, quick sort would have the exact same O(n log n) shape as merge sort — log(n) levels of recursion, O(n) partitioning work at each level. But partitioning only produces two balanced halves if the pivot happens to land near the median of the current subarray. Choosing the pivot poorly can produce wildly unbalanced splits:
typescript
Every partition peels off exactly one element instead of roughly halving the remaining problem — this degenerates into O(n) levels of recursion instead of O(log n), each still doing O(n) partitioning work, for an overall O(n²) worst case. This is structurally the identical failure mode as Module P-5's BST degenerating on sorted input: a strategy that's efficient on average can become linear-chain-like on specifically adversarial input, and "already sorted" turns out to be exactly that adversarial case for a naive last-element pivot choice.
The fix: choosing the pivot randomly, or using a "median-of-three" heuristic (comparing the first, middle, and last elements and picking the median of those three as the pivot), makes the already-sorted worst case extremely unlikely to trigger in practice — not impossible in theory, but no longer something an ordinary "the input happened to already be sorted" scenario will hit. This is why production quicksort implementations essentially never use "always pick the last element" in practice.
The Honest Trade-Off vs. Merge Sort
Merge Sort (P-9)
Quick Sort (P-10)
Average time
O(n log n)
O(n log n)
Worst case
O(n log n) — guaranteed
O(n²) — rare with good pivot choice, but possible
Space
O(n) auxiliary
O(log n) — just the recursive call stack
Stable?
Yes
No, not inherently — partitioning's swaps can reorder equal elements
In-place?
No — needs a second array to merge into
Yes
Neither sort is universally "better" — this table is the concrete version of the Module F-1 lesson that Big-O alone doesn't tell you everything about production behavior. When a guaranteed worst case and stability matter more than memory (external sorting, correctness-critical multi-key sorts), merge sort's trade-offs win. When memory footprint and typical-case speed matter more than a guaranteed worst case, quicksort's trade-offs win — which is exactly why many general-purpose sort implementations historically defaulted to a quicksort variant, sometimes with a heap-sort fallback (an introsort) specifically to cap the worst case at O(n log n) if the recursion depth suggests a pivot-choice disaster is unfolding.
Where This Shows Up in Your Stack
Array.prototype.sort() history: older JavaScript engines (and many other language standard libraries) historically used quicksort variants for general-purpose sorting, precisely for its in-place, low-memory-overhead behavior — Module P-9 already noted V8's current implementation has moved to a Timsort-family (merge-sort-based) approach for larger arrays specifically to guarantee stability, which quicksort doesn't provide for free.
Quickselect (previewed here, used directly in Module A-2's Kth Largest Element problem) reuses this exact partition function, but only ever recurses into the one side that contains the target rank — since it doesn't need to sort the other side at all, it achieves O(n) average time for "find the Kth largest element," rather than paying for a full O(n log n) sort just to read off one position.
In-memory sorting where stability doesn't matter (sorting a scratch array of numeric scores with no ties that need preserved ordering, for instance) is exactly where quicksort's lower memory footprint is a genuine, real advantage over merge sort with no real downside.
Randomized pivot selection as a defense against adversarial input is a small instance of a broader, recurring idea in production systems: an algorithm with a bad worst case triggered by a specific, predictable input pattern can often be hardened by introducing randomness that makes that specific pattern no longer reliably reachable by an adversary (or by ordinary, unlucky real-world data) — the same spirit as randomizing hash seeds to prevent deliberately engineered hash-flooding attacks against Module F-4's hash maps.
Summary
Quick sort partitions around a pivot so every element left of it is smaller and every element right of it is larger, using the identical three-pointer, single-pass shape as Module F-8's sortColors.
Because partitioning does the "combining" work upfront, no merge step is needed afterward — quick sort sorts in place, using only O(log n) space (the recursive call stack) versus merge sort's O(n) auxiliary array.
Average case is O(n log n), identical to merge sort, achieved when the pivot lands reasonably close to the median at each level.
Worst case is O(n²), triggered when the pivot choice repeatedly produces wildly unbalanced splits — already-sorted input with a naive "always pick the last element" pivot is the textbook example, structurally identical to Module P-5's BST degeneration.
Randomized or median-of-three pivot selection makes the worst case practically unreachable, which is why it's the standard approach in real implementations rather than a fixed first/last-element pivot.
Quick sort is not stable — equal elements can be reordered by partitioning's swaps — the direct trade-off against merge sort's guaranteed stability and worst case, in exchange for lower memory use and typically faster real-world performance.
The next module, Dynamic Programming I: Memoization and Tabulation, returns to the exponential-blowup problem first flagged in Module P-1's naive Fibonacci — and shows the systematic technique for fixing it.
Knowledge Check
Why doesn't quick sort need a separate "merge" step after its two recursive calls, unlike merge sort?
Why does calling quickSort on already-sorted input, always choosing the last element as the pivot, produce the O(n²) worst case rather than the typical O(n log n)?
According to the module, why is quick sort generally not considered a stable sort, in contrast to merge sort?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
functionpartition(arr:number[], low:number, high:number):number{const pivot = arr[high];// choosing the last element as the pivot (one common, simple choice)let i = low -1;// boundary of "confirmed smaller than pivot"for(let j = low; j < high; j++){if(arr[j]< pivot){ i++;[arr[i], arr[j]]=[arr[j], arr[i]];// swap into the "smaller" region}}[arr[i +1], arr[high]]=[arr[high], arr[i +1]];// place the pivot in its final positionreturn i +1;// the pivot's final, correct index}
functionquickSort(arr:number[], low =0, high = arr.length -1):number[]{if(low < high){const pivotIndex =partition(arr, low, high);quickSort(arr, low, pivotIndex -1);// recursively sort everything left of the pivotquickSort(arr, pivotIndex +1, high);// recursively sort everything right of the pivot}return arr;}
// Already-sorted input, always choosing the LAST element as pivot:quickSort([1,2,3,4,5]);// partition([1,2,3,4,5]) picks pivot = 5 → everything is already smaller → split is [1,2,3,4] | [] | 5// partition([1,2,3,4]) picks pivot = 4 → split is [1,2,3] | [] | 4// partition([1,2,3]) picks pivot = 3 → split is [1,2] | [] | 3// ... every partition produces a split of (n-1) and (0) — no reduction in problem size at all