Sorting
Sorting Algorithms You Should Know
Learn these to understand divide and conquer, not to use them. The built-in sort is faster than anything you will write, and knowing that is part of the answer.
Merge sort - split, sort, merge
Halve the array until each piece has one element, then merge the pieces back in order. Always O(n log n), and stable.
Merge sort
javascript
function mergeSort(items) {
if (items.length <= 1) return items
const mid = Math.floor(items.length / 2)
const left = mergeSort(items.slice(0, mid))
const right = mergeSort(items.slice(mid))
return merge(left, right)
}
function merge(left, right) {
const out = []
let i = 0
let j = 0
while (i < left.length && j < right.length) {
// <= keeps equal elements in order, which is what makes it stable.
if (left[i] <= right[j]) out.push(left[i++])
else out.push(right[j++])
}
while (i < left.length) out.push(left[i++])
while (j < right.length) out.push(right[j++])
return out
}
console.log(mergeSort([5, 2, 9, 1, 7])) // [1, 2, 5, 7, 9]O(n log n) guaranteed, O(n) extra space for the copies. The two trailing while loops handle whichever side still has elements left.
Quicksort - partition around a pivot
Pick a pivot, move everything smaller to one side and larger to the other, then sort each side. Usually the fastest in practice, but O(n squared) on a bad pivot.
Quicksort
javascript
function quickSort(items) {
if (items.length <= 1) return items
// A middle pivot avoids the worst case on already-sorted input,
// which is exactly when a first-element pivot degrades to O(n squared).
const pivotIndex = Math.floor(items.length / 2)
const pivot = items[pivotIndex]
const smaller = []
const equal = []
const larger = []
for (const n of items) {
if (n < pivot) smaller.push(n)
else if (n > pivot) larger.push(n)
else equal.push(n)
}
return [...quickSort(smaller), ...equal, ...quickSort(larger)]
}
console.log(quickSort([5, 3, 8, 1])) // [1, 3, 5, 8]This version is written for clarity, not speed - a real quicksort partitions in place. Note the separate equal bucket: without it, arrays of many duplicates degrade badly.
Counting sort - when the range is small
If you are sorting integers within a known narrow range, you can beat O(n log n) by counting rather than comparing.
Counting sort
javascript
// Ages 0-120, a million people: O(n), not O(n log n).
function countingSort(nums, max) {
const counts = new Array(max + 1).fill(0)
for (const n of nums) counts[n]++
const out = []
for (let value = 0; value <= max; value++) {
for (let i = 0; i < counts[value]; i++) out.push(value)
}
return out
}
console.log(countingSort([3, 1, 2, 3, 1], 3)) // [1, 1, 2, 3, 3]O(n + k) where k is the range. Brilliant for ages or ratings; useless for arbitrary numbers, where k dwarfs n.
The comparison
- Merge sort - O(n log n) always, O(n) space, stable. Predictable.
- Quicksort - O(n log n) typical, O(n squared) worst, O(log n) space. Usually fastest.
- Counting sort - O(n + k), only for small integer ranges.
- Built-in sort - O(n log n), stable, and beats all of the above in real code.
The reason to know these: why is your sort O(n log n)? is a real interview question, and "because comparison sorting cannot do better" is the answer.