Divide and merge
Merge sort splits the array in half, sorts each half by the same method, then merges the two sorted halves into one. The merge walks both halves with two fingers, repeatedly taking the smaller front element.
The recurrence
- Splitting costs little; the real work is the merge, which touches every element once per level.
- The array halves at each level, so the number of levels grows slowly with the size.
- Total work is the per level cost times the number of levels, which the master theorem resolves to a linearithmic running time.
Strengths
- It is stable: equal elements keep their original order.
- Its running time is the same in the best, average, and worst cases, with no bad input.
- It is the natural choice for external sorting of data too large for memory, since merging streams sequentially.
Costs
- The standard version needs extra space the size of the array for the merge buffer.
- For purely in memory arrays its constant factors can lag behind a well tuned quicksort.
Key idea
Merge sort divides, recursively sorts halves, and merges; its recurrence gives a stable, predictable linearithmic time at the cost of extra space.