Merge Sort
The idea
Two sorted piles of exam papers need to become one. You never search: just look at the top paper of each pile and take the smaller. Repeat until both piles are empty. Merge sort builds everything out of exactly this trick.
The problem
The quadratic sorts compare almost everything with almost everything. Merge sort refuses: split the list in half, sort each half, then MERGE the two sorted halves — which is easy, because you only ever need to compare the two front items. Split all the way down to single items and every piece is trivially sorted.
Why it's slow
Merge sort is the first FAST sort in this app. Splitting makes about log₂(n) levels and each level does at most n comparisons: O(n log n) total. Our reversed 8-item test needs under 28 comparisons where bubble sort needs exactly 28 — and the gap explodes with size: a million items cost ~20 million comparisons instead of ~500 billion. The price: it needs extra memory to hold the halves while merging.
Pseudocode
-
split the list in half, again and again, down to single items
Explain this line
A single item is already sorted — that is the bottom of the split.
-
merge two sorted halves back together
Explain this line
The highlighted range shows which two halves are merging.
-
compare the front items of the two halves
Explain this line
Only fronts are ever compared — that is why merging is cheap.
-
copy the smaller one into the next slot
Explain this line
Values are copied into place, not swapped.
-
keep merging until one sorted list remains
Explain this line
Each level of merging doubles the size of the sorted pieces.
Complexity
| Best | Average | Worst | Space |
|---|---|---|---|
| O(n log n) | O(n log n) | O(n log n) | O(n) |
The dependable one: n log n no matter what the input looks like, and stable too. Costs extra memory for the merge buffers.
Code
python
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]java
void mergeSort(int[] a, int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) / 2;
mergeSort(a, lo, mid);
mergeSort(a, mid + 1, hi);
int[] tmp = new int[hi - lo + 1];
int i = lo, j = mid + 1, k = 0;
while (i <= mid && j <= hi)
tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
System.arraycopy(tmp, 0, a, lo, tmp.length);
}cpp
void mergeSort(std::vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) / 2;
mergeSort(a, lo, mid);
mergeSort(a, mid + 1, hi);
std::vector<int> tmp;
int i = lo, j = mid + 1;
while (i <= mid && j <= hi)
tmp.push_back(a[i] <= a[j] ? a[i++] : a[j++]);
while (i <= mid) tmp.push_back(a[i++]);
while (j <= hi) tmp.push_back(a[j++]);
std::copy(tmp.begin(), tmp.end(), a.begin() + lo);
}javascript
function mergeSort(a) {
if (a.length <= 1) return a;
const mid = a.length >> 1;
const left = mergeSort(a.slice(0, mid));
const right = mergeSort(a.slice(mid));
const out = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
out.push(left[i] <= right[j] ? left[i++] : right[j++]);
}
return out.concat(left.slice(i), right.slice(j));
}dart
List<int> mergeSort(List<int> a) {
if (a.length <= 1) return a;
final mid = a.length ~/ 2;
final left = mergeSort(a.sublist(0, mid));
final right = mergeSort(a.sublist(mid));
final out = <int>[];
var i = 0, j = 0;
while (i < left.length && j < right.length) {
out.add(left[i] <= right[j] ? left[i++] : right[j++]);
}
return out
..addAll(left.sublist(i))
..addAll(right.sublist(j));
}