Merge Sort

Split the array in half recursively until each piece is one element, then merge pairs of sorted pieces back together. The merge step walks two sorted lists in lockstep, which is linear and naturally stable.

Linked lists (no random access needed), files that don't fit in RAM (classic external sort), and anywhere stability plus a guaranteed O(n log n) worst case are both required. Parallelizes cleanly across cores or machines.

Memory is scarce. Textbook merge sort needs O(n) auxiliary space, which rules it out on small embedded targets or when you're already near your memory ceiling.