Merge Sort

By Victor Arce

Merge sort takes a different strategy from bubble, selection, and insertion sort: instead of nudging values around one array, it dividesDivide: split the problem into smaller subproblems — here, halves of the array. the list in half again and again until every piece is a single element, then mergesMerge: combine two already-sorted runs into one sorted run by comparing their fronts. those pieces back together in order. This "divide and conquer" idea makes it reliably fast — O(n log n) — no matter how the input is arranged.

Step through it below. The array splits downward into halves; once a piece is a single element it is trivially sorted; then sibling pieces merge upward, always taking the smaller front value first. Toggle show log to follow along in words.

How it works

There are two phases:

1. Divide.Divide: split the problem into smaller subproblems — here, halves of the array. Split the array at the middle into a left and a right half, and keep splitting each half the same way. A piece of length 1 can't be split and is already sorted — those are the leaves of the tree.
2. Merge.Merge: combine two already-sorted runs into one sorted run by comparing their fronts. Take two sorted halves and combine them into one sorted run: look at the front of each half, copy the smaller one out, and advance. Repeat until both halves are emptied. Because each half is already in order, comparing only the fronts is enough.

The recursion does the left subtree all the way down before it merges back up, then the right — exactly the order the steps follow above.

Cost

Each level of the tree touches all n values once during merging, and there are about log₂n levels, so merge sort runs in O(n log n)O(n log n) — linearithmic time: n times log n; the best worst-case for comparison sorts. in the best, average, and worst case — its running time doesn't depend on the input order. The trade-off is memory: the standard merge needs O(n)O(n) — linear time: the work grows in direct proportion to the number of items n. extra space for the output runs (it is not in-place). It is stableStable: equal values keep their original relative order after sorting. when ties take the left value first, which is why it's the basis of many library sorts.

Back to Sorting Algorithms