Quick Sort
Sort in-place by picking a pivot, partitioning around it, and recursively sorting each side ā O(n log n) average with minimal memory.
Intent & Description
šÆ Intent
Sort large arrays in-place with average O(n log n) performance and cache-friendly access ā no auxiliary array needed.
š Context
You need a fast general-purpose sort. Merge sort guarantees O(n log n) but allocates O(n) extra memory. Quick sort achieves the same average performance in-place, and its sequential memory access pattern typically makes it faster on real hardware despite identical asymptotic complexity.
š” Solution
Pick a pivot element (last element, random, or median-of-three). Partition the array so everything smaller goes left of the pivot and everything larger goes right. Recursively sort the left and right partitions. No merge step needed ā the partitioning itself produces the sorted result in-place.
Real-world Use Case
š TL;DR
Fast in-place sort, O(n log n) average. Great cache behavior beats merge sort on real hardware. Watch the pivot ā a naive choice collapses to O(nĀ²) on sorted input.
Advantages
- Average O(n log n) ā fast in practice on real hardware
- In-place ā O(log n) stack space only, no extra array allocated
- Cache-friendly ā accesses contiguous memory sequentially
- Often beats merge sort on arrays despite identical asymptotic complexity
Disadvantages
- Worst case O(nĀ²) ā triggered by already-sorted input with a naive last-element pivot
- Not stable ā equal elements may be reordered relative to each other
- Pivot strategy matters ā naive choice invites bad worst-case; random or median-of-three is much safer
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[arr.length - 1];
const left = [];
const right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
// Usage
const unsorted = [64, 34, 25, 12, 22, 11, 90];
console.log(quickSort(unsorted)); // [11, 12, 22, 25, 34, 64, 90]