Merge Sort
Two sorted runs can be merged by always taking the smaller front value. Start with runs of one and keep doubling until the whole array is one run.
Sort 8 values. Treat each value as a sorted run of one, then merge neighbouring runs.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 15, with their answers.
Left run offers 5, right run offers 1. Which is written next?
Answer: The right one. 1 < 5, so the right run wins.
Left run offers 4, right run offers 2. Which is written next?
Answer: The right one. 2 < 4, so the right run wins.
Left run offers 8, right run offers 3. Which is written next?
Answer: The right one. 3 < 8, so the right run wins.
Left run offers 7, right run offers 6. Which is written next?
Answer: The right one. 6 < 7, so the right run wins.
Left run offers 1, right run offers 2. Which is written next?
Answer: The left one. 1 < 2, so the left run wins.
Left run offers 5, right run offers 2. Which is written next?
Answer: The right one. 2 < 5, so the right run wins.
Left run offers 5, right run offers 4. Which is written next?
Answer: The right one. 4 < 5, so the right run wins.
Left run offers 3, right run offers 6. Which is written next?
Answer: The left one. 3 < 6, so the left run wins.
Left run offers 8, right run offers 6. Which is written next?
Answer: The right one. 6 < 8, so the right run wins.
Left run offers 8, right run offers 7. Which is written next?
Answer: The right one. 7 < 8, so the right run wins.
Left run offers 1, right run offers 3. Which is written next?
Answer: The left one. 1 < 3, so the left run wins.
Left run offers 2, right run offers 3. Which is written next?
Answer: The left one. 2 < 3, so the left run wins.
Left run offers 4, right run offers 3. Which is written next?
Answer: The right one. 3 < 4, so the right run wins.
Left run offers 4, right run offers 6. Which is written next?
Answer: The left one. 4 < 6, so the left run wins.
Left run offers 5, right run offers 6. Which is written next?
Answer: The left one. 5 < 6, so the left run wins.
How it runs, step by step
Sort 8 values. Treat each value as a sorted run of one, then merge neighbouring runs.
Merge sort on 5, 1, 4, 2, 8, 3, 7, 6. Runs of length one are merged into runs of two, then four, and so on.
Pass 1. Every run of 1 value is now sorted, so merge them in pairs.
Pass 1 merges neighbouring sorted runs of length 1.
Copy out 5 and 1, then write them back in order, smaller front value first.
Merging the run at indices 0 to 0 with the run at indices 1 to 1. The smaller of the two front values is written first.
1 is smaller than 5, so 1 is written to index 0.
Writing 1 into index 0 from the right run.
The right run is empty, so the rest of the left run goes down as it is. 5.
Writing 5 into index 1 from the left run.
Copy out 4 and 2, then write them back in order, smaller front value first.
Merging the run at indices 2 to 2 with the run at indices 3 to 3. The smaller of the two front values is written first.
2 is smaller than 4, so 2 is written to index 2.
Writing 2 into index 2 from the right run.
The right run is empty, so the rest of the left run goes down as it is. 4.
Writing 4 into index 3 from the left run.
Copy out 8 and 3, then write them back in order, smaller front value first.
Merging the run at indices 4 to 4 with the run at indices 5 to 5. The smaller of the two front values is written first.
3 is smaller than 8, so 3 is written to index 4.
Writing 3 into index 4 from the right run.
The right run is empty, so the rest of the left run goes down as it is. 8.
Writing 8 into index 5 from the left run.
Copy out 7 and 6, then write them back in order, smaller front value first.
Merging the run at indices 6 to 6 with the run at indices 7 to 7. The smaller of the two front values is written first.
6 is smaller than 7, so 6 is written to index 6.
Writing 6 into index 6 from the right run.
The right run is empty, so the rest of the left run goes down as it is. 7.
Writing 7 into index 7 from the left run.
Pass 2. Every run of 2 values is now sorted, so merge them in pairs.
Pass 2 merges neighbouring sorted runs of length 2.
Copy out 1, 5 and 2, 4, then write them back in order, smaller front value first.
Merging the run at indices 0 to 1 with the run at indices 2 to 3. The smaller of the two front values is written first.
1 is not larger than 2, so 1 is written to index 0.
Writing 1 into index 0 from the left run.
2 is smaller than 5, so 2 is written to index 1.
Writing 2 into index 1 from the right run.
4 is smaller than 5, so 4 is written to index 2.
Writing 4 into index 2 from the right run.
The right run is empty, so the rest of the left run goes down as it is. 5.
Writing 5 into index 3 from the left run.
Copy out 3, 8 and 6, 7, then write them back in order, smaller front value first.
Merging the run at indices 4 to 5 with the run at indices 6 to 7. The smaller of the two front values is written first.
3 is not larger than 6, so 3 is written to index 4.
Writing 3 into index 4 from the left run.
6 is smaller than 8, so 6 is written to index 5.
Writing 6 into index 5 from the right run.
7 is smaller than 8, so 7 is written to index 6.
Writing 7 into index 6 from the right run.
The right run is empty, so the rest of the left run goes down as it is. 8.
Writing 8 into index 7 from the left run.
Pass 3. Every run of 4 values is now sorted, so merge them in pairs.
Pass 3 merges neighbouring sorted runs of length 4.
Copy out 1, 2, 4, 5 and 3, 6, 7, 8, then write them back in order, smaller front value first.
Merging the run at indices 0 to 3 with the run at indices 4 to 7. The smaller of the two front values is written first.
1 is not larger than 3, so 1 is written to index 0.
Writing 1 into index 0 from the left run.
2 is not larger than 3, so 2 is written to index 1.
Writing 2 into index 1 from the left run.
3 is smaller than 4, so 3 is written to index 2.
Writing 3 into index 2 from the right run.
4 is not larger than 6, so 4 is written to index 3.
Writing 4 into index 3 from the left run.
5 is not larger than 6, so 5 is written to index 4.
Writing 5 into index 4 from the left run.
The left run is empty, so the rest of the right run goes down as it is. 6.
Writing 6 into index 5 from the right run.
The left run is empty, so the rest of the right run goes down as it is. 7.
Writing 7 into index 6 from the right run.
The left run is empty, so the rest of the right run goes down as it is. 8.
Writing 8 into index 7 from the right run.
Sorted. 15 comparisons and 24 writes.
Result: the array is sorted in ascending order after 15 comparisons and 24 writes.
Write it yourself
Define mergeSort(values) and return the same values in ascending order. It runs in your browser against this lesson's own 6 examples.
// Sort each half, then merge the two sorted halves by repeatedly taking the smaller front value.function mergeSort(values) { return values;}
Remember
- O(n log n) whatever the input, which is what you buy with the extra memory.
- Stable, as long as a tie takes from the left run.
- Needs O(n) scratch space, so it loses to quick sort when memory is tight.
Topics covered
Related
Where this is used
Languages and runtimesPython's sorted and Java's Arrays.sort on objects
Both run Timsort, a merge sort that first scans for stretches already in order and merges those runs instead of starting from width one. Merge sort is the base because the sort is contractually stable: Java guarantees equal objects keep their original order, and so does Python. Real input tends to arrive partly ordered, so run detection leaves fewer and longer runs to merge than starting from width one would.
Command lineSorting a file larger than memory
GNU sort handles a file that does not fit in RAM by reading a chunk it can sort in memory, writing that chunk to a temporary file, then merging the temporary files together. The merge only ever needs the front value of each run, so memory depends on how many runs you merge at once and not on the size of the file. Every read and write stays sequential, which is the property that makes this cheap on disk.
Storage enginesLSM-tree compaction
RocksDB, LevelDB and Cassandra never edit data in place; they write updates into small sorted files and later compact them. Compaction is the merge step applied to files: take the front key of each sorted file, emit the smallest, and when the same key appears in two files keep the newer one. That is how reads stay fast even though the writes arrived in no particular order.
DatabasesSort-merge join
To join two tables on a key, PostgreSQL can sort both sides by that key and then walk them in step, advancing whichever side is currently smaller. The planner reaches for it when an index already supplies one side in sorted order, or when neither side would fit in memory as a hash table. Once sorted, the join itself is a single pass over both inputs: the merge step with rows instead of numbers.
Why it works this way
Why the merge needs a scratch array
Merging walks two runs at once and writes in sorted order, so the slot you want to write into usually still holds a value you have not read yet. A scratch array gives the output somewhere to go without destroying the input. In-place merges do exist, but they replace one clean linear pass with block rotations and swaps that run slower, so the O(n) buffer is the normal trade.
One character decides whether the sort is stable
Write the comparison as left[i] < right[j] and equal values are taken from the right run, so two records with the same key come out in the opposite order from the one they went in. The fix is the equals sign: left[i] <= right[j]. On plain integers nothing looks wrong, because equal integers are interchangeable. The damage only appears when you sort records by one field after sorting by another and the first sort quietly undoes itself.
Bottom-up doubling is the recursive version with the splitting removed
The recursive form splits down to single elements and then merges on the way back up. When the size is a power of two the two versions perform exactly the same set of merges, just in a different order: the recursion finishes the left half first, the loop finishes each width across the whole array first. For other sizes the run boundaries no longer line up and the loop never does less work than the recursion, usually a little more, because splitting at the midpoint keeps the two halves closer in size than doubling from the left does. Both stay O(n log n), and the loop has no call stack to overflow.
The last group in a round is usually short
a.size is rarely a multiple of width * 2, so the final group of a round can be shorter than a single run. That is what the two min calls are doing: when the leftover is shorter than width, mid equals hi, the right run is empty, and merge just copies the left run through untouched. Drop the hi clamp and any length that is not a power of two reads past the end, starting at three. The mid clamp is needed less often, first at five, where the leftover single element sits past lo + width.
Read more
- Merge sortWikipedia
- TimsortWikipedia
- listsort.txt, the design notes behind CPython's sortCPython · github.com
- External sortingWikipedia
- Comparison sorts visualisedUSF
Next up
- TimSortFind natural ascending runs, extend short ones by insertion sort, then merge neighbouring runs.
- Suffix ArrayThe starting indices of all suffixes, sorted; binary search finds substrings.
- KruskalSort the edges by weight and take each one that joins two different components, which union-find answers.