Сортировка Времени для Гроккинга

Question

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

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

(См . также связанный пост StackOverflow.)

Answer 1

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

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

[...]

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

Answer 2

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

В комментариях к коду говорится:

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

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

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