Грокскинг Timsort

Там (относительно) новый вид в блоке называется Timsort. Он использовался как список Python list.sort и теперь будет новый Array.sort в Java 7.

Там некоторая документация и крошечная статья в Википедии описывая свойства высокого уровня сортировки и некоторые низкоуровневые оценки производительности, но мне было любопытно, может ли кто-нибудь предоставить некоторый псевдокод, чтобы проиллюстрировать, что именно делает Timsort, и каковы ключевые моменты, которые делают его zippy. (Esp. В отношении цитируемой статьи "Оптимистическая сортировка и информационная теоретическая сложность".)

(См. также qaru.site/info/139128/....)

Ответ 1

Цитирование соответствующей части из удаленной записи в блоге: Визуализация алгоритмов сортировки: timestort Python

Бизнес-конец timsort - это объединение, которое работает на запусках предварительно отсортированных элементов. Минимальная минимальная длина minrun длины выполнения, чтобы окончательные слияния были как можно более сбалансированы - для 64 элементов, minrun - это 32. Перед началом слияния производится один проход с помощью данных для обнаружения ранее существовавших прогонов отсортированных элементы. Спускаемые прогоны обрабатываются путем простого их изменения на месте. Если результирующая длина пробега меньше minrun, она увеличивается до minrun, используя сортировку вставки. В перетасованном массиве без значительных ранее существовавших прогонов этот процесс выглядит точно так же, как наше предположение выше: предварительная сортировка блоков элементов minrun с использованием сортировки вставки, прежде чем слияние с сортировкой слияния.

[...]

timsort находит нисходящий прогон и отменяет запуск на месте. Это делается непосредственно на массиве указателей, поэтому кажется "мгновенным" с нашей точки зрения.
Запуск теперь увеличен до длины minrun, используя сортировку вставки.
В начале следующего блока не выполняется прогон, а сортировка вставки используется для сортировки всего блока. Обратите внимание, что отсортированные элементы в нижней части этого блока не обрабатываются специально - timsort не обнаруживает прогоны, которые начинаются в середине блоков, которые были увеличены до minrun.
Наконец, mergesort используется для объединения прогонов.

Ответ 2

Это изменение прошло через список рассылки core-libs, когда он вошел, поэтому есть некоторые обсуждения и полезные ссылки. Здесь web rev с изменениями обзора кода, а также исходный патч.

Комментарии в коде говорят:

Замечание по реализации: эта реализация является стабильной, адаптивной,
итеративный слияние, требующее гораздо меньше n lg (n) сравнений
когда входной массив частично отсортирован, при этом предлагая производительность традиционного объединения, когда входной массив - это случайным образом упорядочивается. Если входной массив почти отсортирован, для реализации требуется приблизительно n сравнений.
Требования временного хранения варьируются от небольшой константы для почти отсортированных входные массивы до n/2 ссылок на объекты для произвольно упорядоченного ввода
массивы.

Реализация принимает равные преимущества по возрастанию и по убыванию в его входном массиве и может воспользоваться преимуществами восходящий и нисходящий порядок в разных частях того же
входной массив. Он хорошо подходит для слияния двух или более отсортированных массивов:
просто объедините массивы и отсортируйте полученный массив.
Реализация была адаптирована из сортировки списка Tim Peters для Python
TimSort. Он использует технику из Питера Макилроя "Оптимистичный
Сортировка и информационная теоретическая сложность", в материалах журнала Четвертый ежегодный симпозиум ACM-SIAM по дискретным алгоритмам, стр. 467-474,
Январь 1993 года.

Похоронен очень полезная ссылка на детали реализации Python, и я думаю, что отличное место для начала, за которым следует код. Чтобы быть невероятно высоким уровнем, timsort повышает производительность, замечая прогоны отсортированных данных и используя эту структуру во время сортировки.