Merge Sort
In plain terms
A stable divide-and-conquer sort that splits, sorts, then merges halves.
Going deeper
Merge sort recursively halves the list, sorts each half, then merges them in order. It guarantees consistent performance and stability, at the cost of extra memory for merging.
Under the hood
Guaranteed O(n log n) and stable, but needs O(n) auxiliary memory; the merge step makes it ideal for external sorting of data too big for RAM.
Examples
Sorting linked lists, external/disk sorts, Python's Timsort (a merge-sort hybrid).
Think of it like...
Like merging two already-sorted piles of papers by repeatedly taking the smaller top sheet from either pile into one combined stack.