Почему сортировка в Java Stream считается стабильной и как это влияет на результат

Что проверяют

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

Как отвечать

Определение: стабильная сортировка сохраняет исходный взаимный порядок элементов, которые компаратор считает равными. Дальше по фактам:

• гарантия из спецификации: для стрима с определённым порядком обхода (encounter order) sorted() стабильна. Такой порядок дают List, массив, LinkedHashSet;
• где гарантии нет: источник без порядка (HashSet, HashMap.values()) или явный вызов unordered(). Стабильность там не обещана, и полагаться на неё нельзя;
• параллельный стрим: для упорядоченного стрима стабильность сохраняется, но платите буферизацией и слиянием, поэтому parallel().sorted() часто медленнее последовательного варианта;
• реализация: для объектов работает Arrays.sort, то есть стабильный TimSort. В IntStream.sorted() сортировка нестабильная, но заметить это нельзя: равные примитивы неразличимы.

Полезное следствие: два последовательных sorted() дают многоуровневую сортировку, если применять их от менее значимого ключа к более значимому. Но в рабочем коде лучше один компаратор: Comparator.comparing(Employee::getSalary).thenComparing(Employee::getName). Это одна сортировка вместо двух и явное намерение.

Упомяните контракт компаратора. Несогласованное сравнение (классика: (a, b) -> (int) (a.getValue() - b.getValue()) с переполнением) даёт IllegalArgumentException: Comparison method violates its general contract! прямо из TimSort. Правильно Integer.compare или Comparator.comparingLong.

Где спотыкаются

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

Собирают результат в Collectors.toMap или groupingBy и теряют порядок. Нужен вариант с фабрикой контейнера и LinkedHashMap.

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