Merge Sort and Divide and Conquer
Sorting by splitting the data in half, sorting each half the same way, then merging two sorted halves in one pass. The splitting gives log n levels and each level costs n, which is where O(n log n) comes from.
What a learner can do afterwards
- Merge two sorted lists into one and count the comparisons the merge needs
- Draw the split-and-merge tree for eight values and count its levels
- Explain why O(n log n) beats O(n squared) badly once the input is large
1 · Read
Merge sort is divide and conquer: you split the data in half, sort each half the same way, then merge the halves. A list of one item or none is already sorted, so that is your base case and all real work sits in the merges.
You merge with two fingers, always copying the smaller front value into the result. Merging 1 4 6 with 2 3 5 takes 5 comparisons and gives 1 2 3 4 5 6. Splitting 8 values down to ones takes 3 levels, since 8 halves to 4, then 2, then 1.
Each level merges all n items with linear work, and there are about log n levels, so the total is order n log n. When n doubles, this work a bit more than doubles, while quadratic work quadruples. That gentle growth is why it beats order n squared badly on large inputs.
You trace it on paper by splitting to ones first, then merging pairs while counting comparisons aloud. Sketch the tree for eight values and check you see three split levels before you trust the running time argument.
Split to ones, merge in order, and log n levels of linear work give n log n.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.