Sorting
Merge Sort Visualiser
Split down to single values, then merge the pieces back in order.
Split the array down to single bars, then merge the pieces back in order.
- Comparisons
- 0
- Writes
- 0
- for scale
- n log₂n ≈ 53
The splitting is the same whatever the values are, which is why this count barely moves between arrangements — and why merge sort has no bad input to avoid. The counter is an exact count for this run; the curve beside it is the shape that count follows as n grows, not a limit on it.
- Being compared
- Being written
- Pivot or smallest so far
- In its final place
- Ruled out
function mergeSort(a, lo = 0, hi = a.length - 1) { if (lo >= hi) return a; // one bar is already sorted const mid = (lo + hi) >> 1; mergeSort(a, lo, mid); mergeSort(a, mid + 1, hi); merge(a, lo, mid, hi); return a;}function merge(a, lo, mid, hi) { const left = a.slice(lo, mid + 1); const right = a.slice(mid + 1, hi + 1); let i = 0, j = 0, k = lo; while (i < left.length && j < right.length) { a[k++] = left[i] <= right[j] ? left[i++] : right[j++]; } while (i < left.length) a[k++] = left[i++]; while (j < right.length) a[k++] = right[j++];}The highlighted line is the one that produced the picture on the left.
What Merge Sort does
Merge sort rests on one observation: merging two already-sorted runs into one sorted run is easy, because you only ever have to look at the front of each. Split the array in half, sort each half the same way, then merge. The splitting bottoms out at single values, which are sorted by definition.
How it works, step by step
- If the range holds one value or none, it is already sorted. Return.
- Split the range in half and sort the left half, then the right half, by the same method.
- Merge the two sorted halves: repeatedly take whichever front value is smaller and write it to the output.
- When one half runs out, copy the rest of the other across unchanged.
What to watch for
- The bracket under the bars shows the range being worked on. It shrinks all the way down before anything is merged.
- During a merge, only the front of each run is ever compared, so the whole merge is linear in the size of the range.
- Every level of the split touches all n values and the array halves each time, so there are about log₂n levels: that product is the n log n.
- Equal values keep their original order because the merge takes from the left run on a tie. That one `<=` is the whole of its stability.
Cost
| Best case | O(n log n) |
|---|---|
| Average | O(n log n) |
| Worst case | O(n log n) |
| Extra space | O(n) |
| Stable | Yes |
When to reach for it
When you need a guarantee rather than an average: merge sort is n log n on every input, including the ones that make quicksort degrade. It is also the natural choice when stability matters, or when the data is on disk and arrives as sorted runs. The cost is the extra array it needs.