Merge sort
Cut the array in half, sort each half, then merge the two sorted halves by repeatedly taking the smaller front item. The halving is what makes it n log n.
53819274
Press play or step forward to start.
1function mergeSort(a, lo, hi) {2 if (lo >= hi) return;3 const mid = Math.floor((lo + hi) / 2);4 mergeSort(a, lo, mid);5 mergeSort(a, mid + 1, hi);6 merge(a, lo, mid, hi);7}89function merge(a, lo, mid, hi) {10 const left = a.slice(lo, mid + 1);11 const right = a.slice(mid + 1, hi + 1);12 let i = 0, j = 0, k = lo;13 while (i < left.length && j < right.length) {14 if (right[j] < left[i]) a[k++] = right[j++];15 else a[k++] = left[i++];16 }17 while (i < left.length) a[k++] = left[i++];18 while (j < right.length) a[k++] = right[j++];19}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n log n | every input: the splits never change |
| average | n log n | random input |
| worst | n log n | no bad input exists |
| space | n | the copies of each half while merging |
Where it breaks
- Memory. Every merge copies its two halves, so it needs n extra slots. Quicksort and heapsort do not, which is why they win when memory is tight.
- Small arrays. All that splitting and copying costs more than it saves on a handful of items. Real implementations hand short ranges, a few dozen items or fewer, to insertion sort.
- Stability depends on one character. Taking from the left half on a tie keeps equal items in order. Change
<to<=in the merge and it quietly stops being stable.