Split the problem into independent halves, solve each, then combine the answers.
Used for
[3, 6] and [2, 8]
2 < 3, then 3 < 8, ...
Merging [3, 6] and [2, 8]. Which number goes first?
Not quite. Compare the two front numbers: 2 is smaller than 3, so 2 goes first.
Step 1 of 6
Goal: sort [6, 3, 8, 2]. Big problems are hard and tiny ones are easy. Split in half until every piece is a single number (already sorted), then join the pieces back together in order.
Step 2 of 6
Split into [6, 3] and [8, 2].
Step 3 of 6
Split again until each piece is one number. One number is always sorted.
Step 4 of 6
Join neighbours in order: [6, 3] becomes [3, 6] and [8, 2] becomes [2, 8].
Step 5 of 6
Join the two sorted halves by repeatedly taking the smaller front number: 2, 3, 6, 8. There are about log n levels of splitting and each level handles every number once, so n log n. Solving halves and combining the answers is divide and conquer.
Step 6 of 6
Your turn.
RecursionMerge SortQuicksortFast Powering AlgorithmTower of HanoiBinary Search
function mergeSort(a) { if (a.length < 2) return a; const mid = a.length >> 1, l = mergeSort(a.slice(0, mid)), r = mergeSort(a.slice(mid)); const out = []; while (l.length && r.length) out.push(l[0] <= r[0] ? l.shift() : r.shift()); return [...out, ...l, ...r];}