Stable Sorting

Elements equal by key still have an order

A sort is called stable if elements that are equal according to the chosen criterion keep the same relative order after sorting that they had before it. For an array of plain numbers, this is often invisible because equal numbers are indistinguishable.

The difference matters when an element contains additional data. Imagine tasks with “name” and “priority” fields. If two tasks have the same priority, a stable sort by priority preserves their original relative order.

record Task(String name, int priority) {}

Task[] tasks = {
    new Task("A", 2),
    new Task("B", 1),
    new Task("C", 2)
};

Arrays.sort(tasks, Comparator.comparingInt(Task::priority));

If the sorting operation is stable, then among tasks with priority 2, A remains before C because that was their order in the input.

Why stability matters in practice

Stability is especially useful when data is sorted successively by several fields. For example, records can first be ordered by name and then, using a stable sort, by group. Inside each group, the previous name order is preserved.

Stability depends on the implementation

The name of a sorting idea alone is not always enough to determine the behavior of a particular implementation. For example, ordinary insertion sort can be stable if equal elements never move past one another, while a careless change to the comparison condition can destroy that property.