TimSort

Find runs of already-ordered data in the input, extend short runs using insertion sort, then merge the runs with a carefully balanced stack that keeps merges roughly equal-sized. Adapts to whatever structure is already present.

Real-world data — which is almost never random. Stable, O(n) on presorted input, O(n log n) worst case. It's the default sort in Python, V8 (Chrome/Node.js), Rust's stable sort, Swift, and Java's Arrays.sort for objects.

You're writing a minimal or embedded implementation. The algorithm is intricate — galloping mode, minrun computation, merge-stack invariants — and a plain mergesort is much easier to audit when you only need the guarantees.