Quick Sort
Quick sort is the most widely used sorting algorithm in practice. Despite having the same average-case complexity as merge sort (O(n log n)), it is often 2–3x faster in real benchmarks because it sorts in-place (no extra array allocation) and has excellent cache locality.
Understanding quick sort deeply — both Lomuto and Hoare partition schemes, the randomization trick, and the Dutch National Flag three-way partition — is valuable for interviews and systems programming.
The Core Idea: Partition
Quick sort picks a pivot element, then partitions the array so that:
- All elements less than the pivot are to its left
- All elements greater than the pivot are to its right
- The pivot is in its final sorted position
After one partition, the pivot is placed correctly. Recursively sort the left and right subarrays. The pivot does not need to be included in any recursive call — it is already in its final position.
Lomuto Partition Scheme
Lomuto uses the last element as the pivot. It maintains a boundary i such that all elements in arr[lo..i] are ≤ pivot. Simpler to understand and implement than Hoare, but makes more swaps.
function quickSortLomuto(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return arr;
const pivotIdx = partitionLomuto(arr, lo, hi);
quickSortLomuto(arr, lo, pivotIdx - 1); // sort left subarray
quickSortLomuto(arr, pivotIdx + 1, hi); // sort right subarray
return arr;
}
function partitionLomuto(arr, lo, hi) {
const pivot = arr[hi]; // choose last element as pivot
let i = lo - 1; // i: boundary of "less than pivot" region
for (let j = lo; j < hi; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]]; // move small element into left region
}
}
// Place pivot in its final sorted position
[arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
return i + 1; // pivot's final index
}
// Example trace: [3, 6, 8, 10, 1, 2, 1], pivot = arr[6] = 1
// i starts at -1. j scans:
// j=0: arr[0]=3 > 1, skip
// j=1: arr[1]=6 > 1, skip
// ...
// j=4: arr[4]=1 <= 1, i=0, swap(arr[0],arr[4]): [1,6,8,10,3,2,1]
// j=5: arr[5]=2 > 1, skip
// j=6: done. Swap(arr[1],arr[6]): [1,1,8,10,3,2,6]
// Pivot (1) is now at index 1. ✓Hoare Partition Scheme
Hoare uses the first element as pivot and two inward-moving pointers. It makes fewer swaps than Lomuto and handles equal elements better. The partition index returned is NOT the pivot's final position — both subarrays include the partition index.
function quickSortHoare(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return arr;
const p = partitionHoare(arr, lo, hi);
quickSortHoare(arr, lo, p); // NOTE: includes p (not p-1!)
quickSortHoare(arr, p + 1, hi);
return arr;
}
function partitionHoare(arr, lo, hi) {
const pivot = arr[lo]; // first element as pivot
let i = lo - 1, j = hi + 1;
while (true) {
do { i++; } while (arr[i] < pivot); // advance i rightward past small elements
do { j--; } while (arr[j] > pivot); // advance j leftward past large elements
if (i >= j) return j; // pointers crossed — done
[arr[i], arr[j]] = [arr[j], arr[i]]; // swap out-of-place elements
}
}
// Hoare makes 3x fewer swaps on average than Lomuto
// and handles duplicate elements more efficientlyThe Worst Case: Sorted Input
// Sorted array is the worst case for naive quicksort with last-element pivot const sorted = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; // Partition always selects 10 as pivot, 1-9 go left, nothing goes right // Recursion depth = n, comparisons = n + (n-1) + ... + 1 = n²/2 = O(n²) // Also bad: all elements equal const equal = [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]; // Lomuto always puts everything on one side → O(n²) // 3-way partition (Dutch National Flag) handles this in O(n)
Randomized Quick Sort
The fix for the worst case: randomly select the pivot. With a random pivot, the probability of consistently picking a bad pivot is astronomically small. The expected time complexity becomes O(n log n) with very high probability — making the worst case essentially impossible in practice (you would need extremely bad luck on every single partition).
function quickSortRandom(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return arr;
// Randomly choose a pivot and swap it to the end (for Lomuto)
const randomIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
[arr[randomIdx], arr[hi]] = [arr[hi], arr[randomIdx]];
const pivotIdx = partitionLomuto(arr, lo, hi);
quickSortRandom(arr, lo, pivotIdx - 1);
quickSortRandom(arr, pivotIdx + 1, hi);
return arr;
}
// Expected: O(n log n) for ANY input
// Worst case: O(n²) but with probability < 1/2^n for any fixed n3-Way Partition (Dutch National Flag)
Standard quicksort is O(n²) when all elements are equal — every partition puts everything on one side. The 3-way partition (Dutch National Flag, by Dijkstra) handles duplicates optimally: it groups elements into three regions — less than, equal to, and greater than the pivot.
This reduces the time to O(n) when all elements are equal, and O(n log n) in general. It is essential for inputs with many duplicates.
function quickSort3Way(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return arr;
// Dutch National Flag partition
// After partition: arr[lo..lt-1] < pivot, arr[lt..gt] == pivot, arr[gt+1..hi] > pivot
let lt = lo, gt = hi;
const pivot = arr[lo];
let i = lo;
while (i <= gt) {
if (arr[i] < pivot) {
[arr[lt], arr[i]] = [arr[i], arr[lt]];
lt++;
i++;
} else if (arr[i] > pivot) {
[arr[i], arr[gt]] = [arr[gt], arr[i]];
gt--;
// DO NOT increment i — the element swapped from gt has not been inspected yet
} else {
i++; // arr[i] === pivot, skip
}
}
// Now arr[lo..lt-1] < pivot, arr[lt..gt] == pivot, arr[gt+1..hi] > pivot
// Only recurse on the less-than and greater-than regions — skip all equals!
quickSort3Way(arr, lo, lt - 1);
quickSort3Way(arr, gt + 1, hi);
return arr;
}
// Test on array with many duplicates
quickSort3Way([3, 5, 8, 5, 5, 2, 5, 5, 8, 3]);
// → [2, 3, 3, 5, 5, 5, 5, 5, 8, 8]
// With 3-way: the 5s are never recursed into → O(n) total for this input!quickSort3Way([3,5,8,5,5,2,5,5,8,3]) → [2,3,3,5,5,5,5,5,8,8]
Quickselect: Finding the Kth Largest Element
Quickselect is quicksort's cousin: instead of sorting both halves, it only recurses into the half that contains the kth element. Expected O(n) time — better than sorting for finding a single order statistic.
// LeetCode 215 — Kth Largest Element in an Array
// k=1 means the largest, k=2 means second largest, etc.
function findKthLargest(nums, k) {
// Convert to "kth smallest from the end" → index = n - k in sorted order
const targetIdx = nums.length - k;
return quickselect(nums, 0, nums.length - 1, targetIdx);
}
function quickselect(arr, lo, hi, k) {
if (lo === hi) return arr[lo];
// Random pivot for expected O(n)
const randomIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
[arr[randomIdx], arr[hi]] = [arr[hi], arr[randomIdx]];
const pivotIdx = partitionLomuto(arr, lo, hi);
if (pivotIdx === k) return arr[pivotIdx];
if (pivotIdx < k) return quickselect(arr, pivotIdx + 1, hi, k);
return quickselect(arr, lo, pivotIdx - 1, k);
}
function partitionLomuto(arr, lo, hi) {
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;
}
findKthLargest([3, 2, 1, 5, 6, 4], 2); // → 5 (2nd largest)
findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4); // → 4Complexity Summary
Average case: O(n log n) — expected with random pivot
Best case: O(n log n) — balanced partitions
Worst case: O(n²) — consistently bad pivot (rare with randomization)
Space: O(log n) average — recursion stack depth (log n balanced splits)
Space: O(n) worst case — degenerate recursion stack
Not stable — equal elements may be reordered during partitions