Quick Overview
Both average `O(N log N)`, but merge sort guarantees it and stays stable at the cost of `O(N)` scratch space. Quick sort sorts in place and degrades to `O(N^2)` on a bad pivot.
Comparison-based sorting has a mathematical theoretical lower bound of O(N log N). Merge Sort and Quick Sort are the two foundational divide-and-conquer sorting algorithms.
Merge Sort divides the array into two halves, recursively sorts each half, and merges the two sorted halves:
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const leftSorted = mergeSort(arr.slice(0, mid));
const rightSorted = mergeSort(arr.slice(mid));
return merge(leftSorted, rightSorted);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// Output: [ 3, 9, 10, 27, 38, 43, 82 ]
Quick Sort picks a pivot element and partitions the array so all elements smaller than the pivot go to the left and larger elements go to the right:
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)];
}
| Algorithm | Best Time | Average Time | Worst Time | Space | Stable? |
|---|---|---|---|---|---|
| Merge Sort | O(N log N) | O(N log N) | O(N log N) | O(N) | Yes |
| Quick Sort | O(N log N) | O(N log N) | O(N^2) (Bad pivot) | O(log N) | No |
O(N^2) quadratic degradation! Use randomized pivot selection in production.Understand sorting guarantees for performance critical systems. Next, let's enter Phase 3 and explore Trees and Traversals!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.