Example 1 — Sort eight numbers level by level
Show the steps and the answer
Split down to single items: [38] [27] [43] [3] [9] [82] [10] [15].
A one-item list is already sorted, the base case. 8 items take 3 levels of halving, since .
Merge pairs: [27, 38], [3, 43], [9, 82], [10, 15], with 1 comparison each, 4 in all.
Merging two single items takes exactly one comparison.
Merge into fours: [27, 38] with [3, 43] gives [3, 27, 38, 43] in 3 comparisons; [9, 82] with [10, 15] gives [9, 10, 15, 82] in 3 comparisons.
Each comparison places the smaller front item, and when one side runs out the rest is copied with no comparison.
Final merge: from [3, 27, 38, 43] and [9, 10, 15, 82], take 3, 9, 10, 15, 27, 38, 43 using 7 comparisons, then copy 82.
The last merge handles all 8 items, so it needs at most 8 − 1 = 7 comparisons.
Total: 4 + 6 + 7 = 17 comparisons.
Each of the 3 levels costs at most about 8, so the bound is ; bubble sort could need .
Answer: [3, 9, 10, 15, 27, 38, 43, 82], using 17 comparisons.
Takeaway: Merge sort does its real work on the way back up: every level merges all n items, and there are about levels.