Mergesort
Mergesort divides an array into halves, recursively sorts each half, and merges them back in O(n log n) time and O(n) space. It is stable and guarantees O(n log n) worst case.
Mergesort = splitting a deck of cards in half repeatedly until you have single cards, then merging sorted piles back together like a zipper. Steady and reliable -- always O(n log n), no bad luck possible.
Unlike quicksort, mergesort is always O(n log n) — no worst-case degradation. It requires O(n) auxiliary space for the merge step. Stable sort: equal elements maintain relative order from the original array (important for multi-key sorting). Used for external sorting (data too large for RAM) — merge k sorted chunks from disk. Java's Arrays.sort for objects uses Timsort, a hybrid of mergesort and insertion sort.
Bottom-up mergesort avoids recursion: start with windows of size 1, merge pairs, double window size, repeat — O(n log n) time, O(n) space, O(1) extra stack. Timsort exploits existing runs (sorted subsequences) in real data — identifies natural runs of length ≥ minRun (32-64 elements), extends short runs with binary insertion sort, then merges runs using a merge stack maintaining invariants that minimize total merge work. This makes Timsort O(n) on nearly-sorted data and O(n log n) worst case. Mergesort on linked lists is O(n log n) with O(1) extra space (merge in-place on lists), making it superior to quicksort for linked lists.
I choose mergesort when I need guaranteed O(n log n), stability, or when working with linked lists (where in-place merging is O(1) extra space). For arrays in memory, quicksort is usually faster due to cache locality. For counting inversions in an array, mergesort is canonical — count how many times during merging you pick from the right array before the left (each such event counts inversions). I've also used the merge step alone for 'merge k sorted lists' problems.
Mergesort is NOT in-place for arrays — it requires O(n) auxiliary space for the merge step. Claiming it's O(1) space is wrong. In-place merge exists (e.g., block merge sort) but is complex and not expected in interviews. Also: merge is O(n) time, not O(1) — it's the step that makes mergesort work, not the recursion alone.