2.2Merge sort
The idea
Merge sort splits the array, sorts both halves and merges them in linear time. It is always Θ(n log n).
Think of it like this: Two sorted piles of cards combined by always taking the smaller top card.
Why it exists
A reliable n log n sort, and the classic example for the recurrence 2T(n/2) + n.
How it works
- Split in the middle.
- Sort each half recursively.
- Merge: compare the two front elements, take the smaller.
- Merging sizes m and n takes at most m + n − 1 comparisons.
Worked example: T(n) = 2T(n/2) + n
Master theorem: log₂ 2 = 1 = k gives Θ(n log n), in best, average and worst case, with Θ(n) extra space.
Now play with it
- →Step through the default input: each merged range lights up.
- →Try an already sorted array: still the same levels.
- Start: 38 27 43 3 9 82 10
- merged [0..0] and [1..1] → 27 38
- merged [2..2] and [3..3] → 3 43
- merged [0..1] and [2..3] → 3 27 38 43
- merged [4..4] and [5..5] → 9 82
- merged [4..5] and [6..6] → 9 10 82
- merged [0..3] and [4..6] → 3 9 10 27 38 43 82
Θ(n log n) always, needs O(n) extra space, stable. Comparisons between n log n / 2 and n log n − n + 1.
Check yourself
Which statement about merge sort is TRUE?
Exam notes (the dense version)
Divide into halves, sort each, merge in linear time: T(n) = 2T(n/2) + n = Θ(n log n) in every case. Needs O(n) extra space and is stable. Merging two sorted lists of sizes m and n takes at most m + n − 1 comparisons. Good for linked lists and external sorting.
Previous year questions: Sorting & Searching (9)
PYQs are grouped by topic, so this is the full set for Sorting & Searching; try the ones that match this subtopic. Open all 9 on the topic page.