Merge sort and "divide and conquer"
In short: Merge sort splits the list into halves down to single elements and merges them back in order: O(n log n) comparisons on any input, at the cost of O(n) extra memory.
Problem
"Sort by price" with 100,000 products
The online shop has grown to 100,000 products. The "Sort by price" button uses insertion sort from the simple sorts.
With 1,000 products insertion sort makes 256,555 comparisons, and the page opens right away. With 100,000 the comparisons are about 2.5 billion. The products are 100 times more, and the work is 10,000 times more: insertion sort is O(n²), because every new price may be compared with all the prices before it.
You need a way where twice as many products give a little more than twice as much work.
The idea
Divide and conquer
How do two people sort a pile of 1,000 invoices by amount? They split it in two, each sorts their half, then they merge: they look at the top invoice of both piles and take the smaller one. Merging two sorted piles is fast: every comparison puts one invoice in its place.
And how does each of them sort their half? The same way: they split it in two. And so on, until one invoice is left. One invoice is already sorted.
This is divide and conquer: the task is split into smaller tasks of the same kind, they are solved with the same method, and their answers are put together. A sort built this way is merge sort.
The method calls itself, so this is recursion, as in the lesson "Recursion". The base case is a list with one price: there is nothing to split.
See it
Split down to one price and merge back
MergeSort splits and calls itself for the two halves. Merge joins two sorted parts. Watch the eight prices go down to single ones and the merges put them in order on the way back:
static int[] MergeSort(int[] prices){ if (prices.Length <= 1) { return prices; } int mid = prices.Length / 2; int[] left = prices[..mid]; int[] right = prices[mid..]; return Merge(MergeSort(left), MergeSort(right));}
static int[] Merge(int[] left, int[] right){ int[] merged = new int[left.Length + right.Length]; int i = 0, j = 0, k = 0; while (i < left.Length && j < right.Length) { if (left[i] <= right[j]) { merged[k++] = left[i++]; } else { merged[k++] = right[j++]; } } while (i < left.Length) { merged[k++] = left[i++]; } while (j < right.Length) { merged[k++] = right[j++]; } return merged;}Step by step, in words
- MergeSort gets 8 prices from the catalogue, in no order.
- mid = 4. The range [..mid] makes two new arrays: the left half [45, 12, 80, 33] and the right half [7, 61, 25, 50].
- Each half calls MergeSort on itself and splits again: 4 → 2 → 1.
- A part with one price is already sorted. That is the base case: from here on, the calls start returning.
- Merge joins two sorted parts: it compares their first prices and takes the smaller one. For a pair that is 1 comparison: 4 in the whole row.
- The pairs become groups of four. Every comparison sends one price down, so a row never needs more comparisons than it has prices: 6 here.
- The last merge, [12, 33, 45, 80] with [7, 25, 50, 61]. i and j point at the first price not taken yet on each side: 7 comparisons, 7 prices.
- One side has run out. What is left on the other side (80) is already sorted and goes to the end without comparing.
- 3 levels of splitting (8 → 4 → 2 → 1) and on each level the merging passes every price once: 4 + 6 + 7 = 17 comparisons. With n prices there are log₂ n levels, so the work is about n · log₂ n.
int[] prices = { 45, 12, 80, 33, 7, 61, 25, 50 };Console.WriteLine("Before: [" + string.Join(", ", prices) + "]");Console.WriteLine("After: [" + string.Join(", ", MergeSort(prices)) + "]");Before: [45, 12, 80, 33, 7, 61, 25, 50]After: [7, 12, 25, 33, 45, 50, 61, 80]prices[..mid] is a range: on an array it makes a new array with the elements from 0 up to mid (without it). An int divided by an int is a whole number, so mid is 4 even with 9 prices.The idea
Why it is n · log n
See what each part costs:
- Merging is O(n). Every comparison puts one price into the result, and once one part runs out, the rest of the other goes at the end without comparing. Two parts with n prices in total need at most n − 1 comparisons.
- There are log₂ n levels. Each level halves: 8 prices give 3 levels (8 → 4 → 2 → 1), 100,000 prices give 17. log₂ n is "how many times n halves down to 1".
- On each level the merges pass all n prices once. Pairs, groups of four, halves: the groups differ from level to level, but together they are always n.
In total: at most n · log₂ n comparisons. For 100,000 prices that is under 1,700,000. Bench counts 1,536,292, about 1,600 times fewer than the 2.5 billion of insertion sort.
Try it
Predict the output
Here Merge counts its comparisons. The two parts are sorted, and every price on the left is smaller than every price on the right:
static long comparisons = 0;
static int[] Merge(int[] left, int[] right){ int[] merged = new int[left.Length + right.Length]; int i = 0, j = 0, k = 0; while (i < left.Length && j < right.Length) { comparisons++; if (left[i] <= right[j]) { merged[k++] = left[i++]; } else { merged[k++] = right[j++]; } } while (i < left.Length) { merged[k++] = left[i++]; } while (j < right.Length) { merged[k++] = right[j++]; } return merged;}
Console.WriteLine("[" + string.Join(", ", Merge(new[] { 10, 20, 30 }, new[] { 40, 50, 60 })) + "]");Console.WriteLine("Comparisons: " + comparisons);The three prices on the left come out with one comparison each: 10 against 40, 20 against 40, 30 against 40. Then the left part runs out, and 40, 50 and 60 go at the end without comparing. Merging n prices takes between the length of the shorter part (here 3) and n − 1 (here 5) comparisons. Never more than n.
See it
Measure it: merge sort against insertion sort
Run both algorithms on the same catalog of prices. What is counted is comparisons. Insertion sort is not really run at 100,000 (the page would freeze): Bench estimates it from the curve.
- Insertion sort
O(n²) - Merge sort
O(n log n)
| Algorithm | n = 10 | n = 1,000 | n = 10,000 | n = 100,000 |
|---|---|---|---|---|
| Insertion sort | 32 | 256,555 | 24,738,716 | ≈ 2,473,871,600 |
| Merge sort | 24 | 8,679 | 120,483 | 1,536,292 |
static int[] MergeSort(int[] prices){ if (prices.Length <= 1) { return prices; } int mid = prices.Length / 2; int[] left = prices[..mid]; int[] right = prices[mid..]; return Merge(MergeSort(left), MergeSort(right));}
static int[] Merge(int[] left, int[] right){ int[] merged = new int[left.Length + right.Length]; int i = 0, j = 0, k = 0; while (i < left.Length && j < right.Length) { if (left[i] <= right[j]) { merged[k++] = left[i++]; } else { merged[k++] = right[j++]; } } while (i < left.Length) { merged[k++] = left[i++]; } while (j < right.Length) { merged[k++] = right[j++]; } return merged;}With 10 prices the two are almost equal. With 1,000 merge sort makes 8,679 comparisons against 256,555. From there on the gap grows with every zero: the O(n²) curve is twice as steep.
More precisely, if you are curious
The same numbers in your language. The catalog comes from a small generator with a seed, so it is the same on every run, in every language and in Bench. The counter goes up on every comparison of two prices:
static long comparisons = 0;
static int[] Catalog(int n){ int[] prices = new int[n]; long x = 2026; for (int k = 0; k < n; k++) { x = x * 48271 % 2147483647; prices[k] = 1 + (int)(x % 10000); } return prices;}
static void InsertionSort(int[] prices){ for (int i = 1; i < prices.Length; i++) { int key = prices[i]; int j = i; while (j > 0) { comparisons++; if (prices[j - 1] <= key) { break; } prices[j] = prices[j - 1]; j--; } prices[j] = key; }}
static int[] MergeSort(int[] prices){ if (prices.Length <= 1) { return prices; } int mid = prices.Length / 2; int[] left = prices[..mid]; int[] right = prices[mid..]; return Merge(MergeSort(left), MergeSort(right));}
static int[] Merge(int[] left, int[] right){ int[] merged = new int[left.Length + right.Length]; int i = 0, j = 0, k = 0; while (i < left.Length && j < right.Length) { comparisons++; if (left[i] <= right[j]) { merged[k++] = left[i++]; } else { merged[k++] = right[j++]; } } while (i < left.Length) { merged[k++] = left[i++]; } while (j < right.Length) { merged[k++] = right[j++]; } return merged;}
foreach (int n in new[] { 10, 1000 }){ comparisons = 0; InsertionSort(Catalog(n)); Console.WriteLine($"insertion sort, n = {n}: {comparisons} comparisons");}foreach (int n in new[] { 10, 1000, 100000 }){ comparisons = 0; MergeSort(Catalog(n)); Console.WriteLine($"merge sort, n = {n}: {comparisons} comparisons");}insertion sort, n = 10: 32 comparisonsinsertion sort, n = 1000: 256555 comparisonsmerge sort, n = 10: 24 comparisonsmerge sort, n = 1000: 8679 comparisonsmerge sort, n = 100000: 1536292 comparisonsThe idea
The price: memory
Merge sort is not free. Insertion sort moves the prices inside the list itself and needs no other space. Merge sort makes new arrays on every split, and Merge writes the result into one more. The extra memory is O(n): for 100,000 prices, as much space again.
The call stack is shallow: one frame per level, about log₂ n. For 100,000 prices that is 18 frames.
Equal prices stay in the order they came in: on a tie Merge takes the left one (<=). This is called stability, and it has its own lesson, "Stable sorting".
prices[..mid] on an array makes a copy. On a Span<int> the same range does not copy: it is a view into the same memory. The merge still needs room for the result, so the memory stays O(n).Try it
Find the bug
A catalog of eight products goes in, and four come out:
int[] prices = { 45, 12, 80, 33, 7, 61, 25, 50 };Console.WriteLine("Before: [" + string.Join(", ", prices) + "]");Console.WriteLine("After: [" + string.Join(", ", MergeSort(prices)) + "]");Before: [45, 12, 80, 33, 7, 61, 25, 50]After: [33, 45, 50, 61]Which line has the bug?
Pick the line with the bug.
The right half starts at mid + 1, and the price at mid goes into neither half. Every split loses one price: with 8 prices, 4 are lost. The compiler says nothing and the program does not stop. The left part goes from 0 up to mid without mid, so the right one has to start exactly at mid.
Try it
Fill in the blank
The loop in Merge stops as soon as one part runs out. What goes in the blank so that the rest of the right part goes at the end?
static int[] Merge(int[] left, int[] right)
{
int[] merged = new int[left.Length + right.Length];
int i = 0, j = 0, k = 0;
while (i < left.Length && j < right.Length)
{
if (left[i] <= right[j])
{
merged[k++] = left[i++];
}
else
{
merged[k++] = right[j++];
}
}
while (i < left.Length)
{
merged[k++] = left[i++];
}
while (j < right.Length)
{
merged[k++] = right[];
}
return merged;
}j points at the first price on the right that has not been taken yet. Everything from j on is sorted and bigger than what has been taken so far, so it goes at the end without comparing. If you start from the beginning instead, some prices go in twice.
Exercise
Two warehouses, one price list
Solve the task in your editor.
Two warehouses. The warehouse in Sofia and the warehouse in Varna send their price lists, each already sorted. Read the two lines and print one sorted price list for both. Do not sort again: use Merge from the lesson. The work is O(n), not O(n log n).
12 33 45 807 25 50 61 99All: 7 12 25 33 45 50 61 80 99More tasks
- Count. Add a counter of the comparisons to
Mergeand sort the eight prices from the scene. You should get 17. - Most expensive first. Change one sign so that the list comes out from the most expensive to the cheapest.
- Without recursion. Merge the neighboring single prices into pairs, then the pairs into groups of four, then the fours. This is bottom-up merge sort: the same comparisons, with no call stack.
More precisely
Merging outside sorting
Merging sorted lists is older than merge sort: punched card machines merged sorted decks of cards back in the 1930s. Today it shows up wherever the data is already sorted: in git, in databases, in files bigger than the memory.
More precisely, if you are curious
Git. Git keeps the contents of every folder (a tree) sorted by file name. When it compares two versions or merges branches, it walks the two sorted lists side by side, like Merge: a name that is only on one side is an added or deleted file, and equal names are a file on both sides, which gets compared. So checking a folder is O(n), not a search for every file in the other list. Merging the text inside a file is a different algorithm (diff), which we get to in the dynamic programming module.
External sorting. The site's logs for a year are 50 GB, and the memory is 8 GB. The sort reads 1 GB at a time, sorts it in memory and writes it as a sorted chunk to disk. Then it merges the chunks: from each one it reads only the first line, takes the smallest and goes on. The memory is enough for one line from each chunk. This is how the sort command on Linux sorts big files, and PostgreSQL writes Sort Method: external merge in the query plan when the sort does not fit in its memory.
The master theorem, as an intuition. The time of merge sort is written T(n) = 2 · T(n/2) + n: two tasks of half the size plus n for the merge. Draw it as a tree: at the top there is n work, on the next level two times n/2, which is n again, and so on for log₂ n levels. In total n · log₂ n. The master theorem generalizes exactly this comparison: if the work per level shrinks going down, the top level decides; if it grows, the leaves decide; if it is the same on every level, you multiply by the number of levels. Binary search is T(n) = T(n/2) + 1: 1 per level, log₂ n levels, O(log n).
The built-in sort. In C# Array.Sort and List<T>.Sort are not merge sort but introsort: quick sort that switches to heap sort when the recursion gets too deep. How and why is in the lesson "Stable sorting".
Test