Merge Sort

Merge Sort divides the array, sorts recursively, and merges two sorted halves. Time $\Theta(n \log n)$, additional linear memory.

Stable and predictable. Good as a teaching example for Divide-and-Conquer.

$$T(n)=2T(n/2)+\Theta(n)$$

Merge two sorted runs: Merge Sorted Array [1].

Where used

Stable $O(n \log n)$ reference, external sorting (runs on disk), ancestor of TimSort. Parallelizable over independent halves.

Depth

Merge Sort recursively breaks the input into halves, sorts both parts, and combines them in order. During merging, one pointer points to the smallest unmerged element of each half. The smaller is output until one half is exhausted.

The recursion has logarithmically many levels, and at each level, all elements are processed in total. Classic array implementations use an additional buffer on the order of the input size. By adopting from the left half first in case of equality, stability is achieved.

Difficulty levels

1. Merge two sorted sequences using pointers.
2. Connect work per recursion level and the number of levels.
3. Reuse buffer and ensure stable equality handling.

Pitfalls

After the main loop, the remaining elements of the non-exhausted half must be copied. Incorrect interval boundaries can lead to lost or double-processed elements, especially with odd lengths.