Стабильная сортировка

Равные по ключу элементы тоже имеют порядок

Сортировка называется стабильной, если элементы, равные по используемому критерию, после сортировки сохраняют тот же взаимный порядок, который был до неё. Для массива обычных чисел это часто незаметно, потому что одинаковые числа неотличимы друг от друга.

Разница становится важной, когда у элемента есть дополнительные данные. Представим заявки с полями «имя» и «приоритет». Если две заявки имеют одинаковый приоритет, стабильная сортировка по приоритету сохранит их исходный порядок.

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));

Если используемая сортировка стабильна, то среди задач с приоритетом 2 задача A останется раньше C, потому что так было во входных данных.

Зачем стабильность нужна на практике

Стабильность особенно полезна при последовательной сортировке по нескольким полям. Например, сначала можно упорядочить записи по имени, а затем стабильной сортировкой — по группе. Внутри каждой группы прежний порядок по имени сохранится.

Стабильность зависит от реализации

Одно только название идеи сортировки не всегда достаточно, чтобы угадать поведение конкретного кода. Например, обычная сортировка вставками может быть стабильной, если равные элементы не перескакивают друг через друга, а неосторожное изменение условия сравнения способно это свойство разрушить.