Sorting
Sorting Algorithms You Should Know
Written by Swapnil RajaPublished
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]