TimSort в Java
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 это эксплуатирует автоматически. Повторная сортировка почти отсортированного массива значительно дешевле первичной сортировки случайных данных. Это важно для пайплайнов где данные сортируются инкрементально или приходят из источника с естественным порядком. Java Библиотека | Мы в Телеграм