🕯 TimSort в Java

Arrays.sort(Object[]) и Collections.sort() используют TimSort — алгоритм, разработанный Тимом Петерсом для Python в 2002 году и портированный в Java 7. Для примитивов используется dual-pivot quicksort, но для объектов — только TimSort, и причина этого выбора нетривиальна.

🔹 Почему не quicksort для объектов

Quicksort не стабилен — одинаковые элементы могут поменяться местами. Для примитивов это безразлично: два одинаковых int неразличимы. Для объектов же критично: Comparator может считать два объекта равными по одному критерию, но они остаются разными объектами. Нестабильная сортировка ломает составные компараторы и пользовательские ожидания.

Merge sort стабилен, но требует O(n) дополнительной памяти и не использует частичную упорядоченность входных данных.

🔹 Как работает TimSort

TimSort строится на наблюдении: реальные данные редко полностью случайны. Массивы часто содержат уже упорядоченные подпоследовательности — runs.

Алгоритм:

1. Проходит по массиву, находя естественные runs — уже отсортированные (возрастающие или убывающие) подпоследовательности. Убывающие разворачиваются на месте.

2. Если run короче минимального порога (minRun, вычисляется от размера массива, обычно 32-64 элемента) — расширяется insertion sort'ом. Insertion sort эффективен на почти отсортированных коротких последовательностях.

3. Runs помещаются в стек и сливаются попарно через merge sort. Merge происходит не сразу — алгоритм поддерживает инвариант на стеке runs для гарантии O(n log n) в худшем случае.

🔹 Galloping mode

При слиянии двух runs TimSort переключается в режим gallopping если обнаруживает что элементы из одного run идут длинными сериями подряд. Вместо поэлементного сравнения — бинарный поиск: ищет где именно заканчивается серия из первого run. Это даёт O(n) на уже отсортированных данных вместо O(n log n).

Порог переключения в gallopping — MIN_GALLOP = 7. Если 7 раз подряд «выиграл» один run — переключаемся. Порог динамически адаптируется: если gallopping оказывается неэффективным, порог растёт.

🔹 Сложность

→ Лучший случай (уже отсортированный массив): O(n) — один run, ничего сливать не нужно.
→ Средний и худший: O(n log n).
→ Память: O(n) в худшем случае, но на практике меньше — временный буфер для merge не всегда равен половине массива.

🔹 Практическое следствие

Если данные поступают уже частично отсортированными — TimSort это эксплуатирует автоматически. Повторная сортировка почти отсортированного массива значительно дешевле первичной сортировки случайных данных. Это важно для пайплайнов где данные сортируются инкрементально или приходят из источника с естественным порядком.

══════ Навигация ══════
Вакансии • Задачи • Собесы

🐸 Библиотека джависта

#CoreJava