Merge Sort

Merge sort recursively splits the array in half, sorts each half, and merges them back together. Both halves are sorted, so the merge is a linear scan — $O(n)$. The recursion tree has $\log n$ levels, total work $O(n \log n)$.

The merge

Given two sorted arrays, walk both with two pointers. Append the smaller current value to the output and advance that pointer. When one array is exhausted, append the rest of the other. $O(n_1 + n_2)$ time, $O(n_1 + n_2)$ extra space for the output.

Why it's stable

When two values are equal, take the one from the left array. This preserves the relative order from before the sort. Useful for sorting by secondary keys.

Why it's not in-place

The merge step needs an auxiliary buffer of the combined size. An "in-place" merge sort exists but is complicated and rarely used in practice.

Where you'll see it

• Default sort in Python (Timsort, a merge sort variant)
• Sorting linked lists — merging two sorted linked lists is naturally in-place at the pointer level, even though the array version is not
• External sorting (sorting data too large for memory): partition the input into memory-sized chunks, sort each, then $k$-way merge the chunks back
• Counting inversions in an array — modified merge sort solves it in $O(n \log n)$

Tradeoff vs quicksort

Merge sort gives stronger guarantees: stable, deterministic $O(n \log n)$. Quicksort is in-place and usually faster in practice (better cache behavior), at the cost of an $O(n^2)$ worst case. Choose based on which guarantees matter.