Краткий ответ

Сортировка списка в Java стабильна: если компаратор считает два элемента эквивалентными, то есть возвращает 0, их взаимный порядок сохраняется таким, каким он был до сортировки. Поэтому сотрудники с одинаковым результатом сравнения останутся в исходной последовательности.

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

Исторический контекст

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

Такой подход также делает результаты обработки коллекций предсказуемыми для отчётов, пользовательских интерфейсов и пакетных операций. В Java требование стабильности закреплено в контракте сортировки списков, а не является случайным свойством конкретной реализации.

Постановка проблемы

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

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

Подробное решение

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

Например:

import java.util.*;

List<String> names = new ArrayList<>(List.of("Анна", "Борис", "Олег"));
names.sort(Comparator.comparingInt(String::length));
System.out.println(names);

В результате Анна останется перед Олег, поскольку у обеих строк одинаковая длина, а до сортировки Анна находилась раньше. Борис переместится после них из-за большей длины.

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

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

Ситуация из практики

В интернет-магазине товары сначала загружаются в порядке популярности. Затем их сортируют по категории, чтобы сгруппировать товары одного типа. Требование бизнеса: внутри каждой категории сохранить популярность.

Можно написать компаратор только по категории и применить стабильную сортировку. Это простой вариант: он сохраняет исходный порядок без хранения дополнительного номера позиции, но зависит от того, что исходная последовательность действительно отражает популярность.

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

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

Что кандидаты часто упускают

Гарантирует ли стабильность порядок элементов, для которых компаратор возвращает не ноль, а одинаковый знак?

Нет. Гарантия относится только к элементам, для которых результат сравнения равен 0. Если компаратор возвращает отрицательное или положительное значение, сортировка вправе переставить элементы согласно этому отношению. Само совпадение категории или другого поля не имеет значения, если компаратор фактически различает элементы.

Можно ли получить стабильное многокритериальное упорядочивание несколькими сортировками?

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

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

Что произойдёт, если список не поддерживает изменение элементов?

Стабильность сортировки не отменяет требований к изменяемости списка. Сортировка переставляет элементы, поэтому для неизменяемого списка или представления, запрещающего такие изменения, операция завершится UnsupportedOperationException.

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