Merge Sort
Split the array in half, sort each half recursively, then merge the two sorted halves. Always O(n log n), stable, but needs O(n) extra space.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
Two people each hold a sorted pile of cards. To combine them, look at the top card of each pile, take the smaller one, and repeat. That merge is easy and takes one look per card.
Merge sort uses that trick recursively:
- Divide: split the array into two halves.
- Conquer: sort each half (recursively, until a piece has 1 item, which is already sorted).
- Combine: merge the two sorted halves.
The merge
while (i <= mid && j <= hi)
tmp.push_back(a[i] <= a[j] ? a[i++] : a[j++]);
// then copy whatever is left of either halfUsing <= takes the left item when two are equal, so equal items keep their order: merge sort is stable.
Why always n log n
Halving n repeatedly reaches 1 after log₂ n levels. Each level merges n items in total. So the cost is n log n, for sorted, reversed or random data alike. The price is the O(n) temporary array.
Merge vs quick
| Merge sort | Quick sort | |
|---|---|---|
| Worst case | O(n log n) | O(n²) |
| Extra space | O(n) | O(log n) |
| Stable | yes | no |
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
The array splits down to single items, then merges back up. Watch the two-finger merge at each level.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
#include <vector>
using namespace std;
void merge(int a[], int lo, int mid, int hi) {
vector<int> tmp; // O(n) extra space
int i = lo, j = mid + 1;
while (i <= mid && j <= hi) {
if (a[i] <= a[j]) tmp.push_back(a[i++]); // <= keeps it stable
else tmp.push_back(a[j++]);
}
while (i <= mid) tmp.push_back(a[i++]);
while (j <= hi) tmp.push_back(a[j++]);
for (int k = 0; k < (int)tmp.size(); k++) a[lo + k] = tmp[k];
}
void mergeSort(int a[], int lo, int hi) {
if (lo >= hi) return; // 0 or 1 item: already sorted
int mid = lo + (hi - lo) / 2;
mergeSort(a, lo, mid);
mergeSort(a, mid + 1, hi);
merge(a, lo, mid, hi);
cout << "merged [" << lo << ".." << hi << "]: ";
for (int k = lo; k <= hi; k++) cout << a[k] << " ";
cout << "\n";
}
int main() {
int a[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(a) / sizeof(a[0]);
mergeSort(a, 0, n - 1);
cout << "sorted: ";
for (int x : a) cout << x << " ";
cout << "\n";
}merged [0..1]: 27 38 merged [2..3]: 3 43 merged [0..3]: 3 27 38 43 merged [4..5]: 9 82 merged [4..6]: 9 10 82 merged [0..6]: 3 9 10 27 38 43 82 sorted: 3 9 10 27 38 43 82
05Complexity
| Best case | O(n log n) |
|---|---|
| Average case | O(n log n) |
| Worst case | O(n log n) |
| Extra space | O(n) for the temporary array |
| Stable? | Yes |
| In-place? | No |
log₂ n levels of splitting, and each level does O(n) merging work, so n log n whatever the input.
06Watch
Merge Sort Algorithm
Why this one: Abdul Bari draws the full recursion tree and derives n log n.
Merge sort in 3 minutes
Why this one: The 3-minute visual version.
07Exam lens
Likely questions
- Show the split and merge tree of merge sort on
38, 27, 43, 3, 9, 82, 10. - Write the merge function. Why is merge sort O(n log n) in every case?
- Compare merge sort and quick sort (time, space, stability).
Common mistakes
- Forgetting to copy the leftover items after one half runs out.
- Using
<instead of<=in merge, which breaks stability. - Base case
lo > hionly. A single item (lo == hi) must also stop the recursion. - Calling merge sort in-place.
08Quick check
09Practice
🟢 Trace by hand
Trace merge sort on 38, 27, 43, 3, 9, 82, 10. Write every merge in the order it happens.
Show answer
- merge [0..1]:
27 38 - merge [2..3]:
3 43 - merge [0..3]:
3 27 38 43 - merge [4..5]:
9 82 - merge [4..6]:
9 10 82 - merge [0..6]:
3 9 10 27 38 43 82
🟡 Implement it
Count inversions (pairs i < j with a[i] > a[j]) by modifying merge sort.
Hint
When you take from the right half, every item left in the left half is bigger, so add mid − i + 1.
🔴 Solve problems
Hint
Merge from the back so you don't overwrite nums1.
Hint
Merge sort on a linked list. Find the middle with fast/slow pointers, split, sort, merge.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.