Algorithms / Merge Sort Divide Conquer

Least You Need to Know: Merge Sort, Divide-and-Conquer, and Recurrence Reasoning

Merge sort is the classic divide-and-conquer sorting example: split the array, sort each half recursively, then merge the two sorted halves. Its main reasoning patterns are recurrence setup, combine-step cost, and the distinction between guaranteed `O(n log n)` time and the extra linear auxiliary memory used by the common array implementation.

The least you need to know

Merge sort divides into two subproblems of about half size, then merges in linear time.
The recurrence is `T(n) = 2T(n/2) + Theta(n)` under the standard balanced split model.
The merge step is linear because each pointer advances monotonically.
Standard array merge sort is stable and guarantees `O(n log n)` time.
The usual array implementation uses extra auxiliary space during merging.

Key notation

T(n) = 2T(n/2) + Theta(n) standard recurrence for balanced merge sort

stable equal keys preserve relative order

merge combine two sorted lists into one sorted list

Tiny worked example

Split an array of length `n` into left and right halves.
Recursively sort each half.
Merge the two sorted halves by repeatedly taking the smaller front element.
Because the merge touches each element once, the combine step is linear.

Common mistakes

Students sometimes forget that the `log n` levels come from repeated halving, not from the merge itself.
The merge step is easy to reason about with two advancing pointers.
Guaranteed `O(n log n)` time does not mean in-place memory usage in the usual array version.

How to recognize this kind of problem

The prompt says divide into halves, solve recursively, then combine.
A recurrence or recursion-tree explanation is expected.
Stability or guaranteed worst-case `O(n log n)` is part of the comparison.