Stable Sort Definition Importance

A sort is stable if elements that are equal on the sort key keep their original relative order after sorting. So if I'm sorting people by age and two people are both thirty, a stable sort guarantees they appear in the same order they were in the input, while an unstable sort is free to swap them. It's important to note this is not about correctness; both stable and unstable sorts produce fully sorted output. Stability only governs what happens to elements that tie on the key. The reason it matters in practice is multi-key sorting. Say I want to sort employees primarily by department and, within each department, by name. The clean way is to sort by the secondary key, name, first, and then do a stable sort by the primary key, department. Because the second sort is stable, it preserves the name ordering I established within each department, so I get the combined ordering I want. If that second sort were unstable, it would scramble the names within each department and ruin the effect. Stability also matters whenever the original input order itself carries meaning, like insertion or arrival time. As for which sorts are stable: merge sort and insertion sort are stable, and so is TimSort, which is what Java uses for objects, and counting sort. Quicksort, heap sort, and selection sort are not stable. One last point: for primitive values stability is irrelevant, because two equal integers are genuinely identical, there's nothing to preserve. In Java I'd usually express multi-key sorting in one stable step using Comparator dot comparing then thenComparing.