Гроккинг Тимсорт

Question

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

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

(См. Также сообщение, связанное с StackOverflow .)

Answer 1

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

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

[...]

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

Answer 2

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

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

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

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

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