Временная сортировка
-
Обзор сортировки Timsort
- Timsort — это алгоритм сортировки, разработанный Тимом Питерсом в 2001 году.
- Он сочетает в себе преимущества быстрой сортировки и сортировки слиянием, обеспечивая стабильную сортировку.
- Timsort использует гибридный подход, объединяя сортировку вставками и сортировку слиянием.
-
Структура и работа Timsort
- Timsort работает с тремя запусками одновременно, сохраняя инварианты их размеров.
- Он использует бинарный поиск для определения местоположения элементов в запусках.
- Timsort выполняет слияние в обоих направлениях и использует скачущий режим для оптимизации слияния.
-
Оптимизация и анализ
- Timsort оптимизирует количество перемещений элементов и временные затраты.
- В худшем случае он имеет сложность O(n log n), а в лучшем случае — линейное время.
- Он превосходит Quicksort в сортировке ссылок на объекты благодаря более эффективному доступу к данным.
-
Формальная проверка и исправления
- В 2015 году была обнаружена ошибка в реализации Timsort, которая была исправлена.
- Исследователи обнаружили, что реализация не проверяла инварианты для всех групп из трех запусков.
- Java и Android версии были исправлены путем увеличения размера стека.
-
Рекомендации
- Для дальнейшего чтения рекомендуется ознакомиться с работами Оже, Жюге, Нико и Пивото.
- Ссылки на внешние ресурсы также предоставлены.