Почему Collections.sort использует сортировку слиянием вместо быстрой?

Мы знаем, что быстрая сортировка - это самый быстрый алгоритм сортировки.

JDK6 collections.sortиспользует алгоритм сортировки слиянием вместо быстрой сортировки. Но Arrays.sort использует алгоритм быстрой сортировки.

В чем причина того, что Collections.sort использует сортировку слиянием вместо быстрой сортировки?

Скорее всего, от Джоша Блоха § :

Я написал эти методы, поэтому полагаю, что могу ответить. Это правда, что не существует единого лучшего алгоритма сортировки. QuickSort имеет два основных недостатка по сравнению с сортировкой слиянием:

1. Это не стабильно (как заметил Парсифаль).

2. Это не гарантирует производительности n log n; он может ухудшиться до квадратичной производительности при патологических входах.

Стабильность - это не проблема для примитивных типов, поскольку нет понятия идентичности, отличного от (значения) равенства. И возможность квадратичного поведения не считалась проблемой на практике для реализации Bentely и McIlroy (или впоследствии для Dual Pivot Quicksort ), поэтому эти варианты QuickSort использовались для примитивных сортировок.

Стабильность очень важна при сортировке произвольных объектов. Например, предположим, что у вас есть объекты, представляющие сообщения электронной почты, и вы сортируете их сначала по дате, а затем по отправителю. Вы ожидаете, что они будут отсортированы по дате в пределах каждого отправителя, но это будет верно только в том случае, если сортировка будет стабильной. Вот почему мы решили обеспечить стабильную сортировку (сортировку слиянием) для сортировки ссылок на объекты. (С технической точки зрения, несколько последовательных стабильных сортировок приводят к лексикографическому упорядочению ключей в порядке, обратном сортировке: окончательная сортировка определяет наиболее значимый подключ.)

Хорошим дополнительным преимуществом является то, что сортировка слиянием гарантирует производительность n log n (время) независимо от входных данных. Конечно, есть и обратная сторона: быстрая сортировка - это сортировка «на месте»: она требует только log n внешнего пространства (для поддержки стека вызовов). С другой стороны, слияние, сортировка требует O (n) внешнего пространства. Вариант TimSort (представленный в Java SE 6) требует значительно меньше места (O (k)), если входной массив почти отсортирован.

Также актуально следующее :

Алгоритм, используемый java.util.Arrays.sort и (косвенно) java.util.Collections.sort для сортировки ссылок на объекты, представляет собой "модифицированную сортировку слиянием" (при которой слияние опускается, если самый высокий элемент в нижнем подсписке меньше, чем самый низкий элемент в верхнем подсписке) ". Это достаточно быстрая стабильная сортировка, которая гарантирует производительность O (n log n) и требует O (n) дополнительного места. В свое время (он был написан в 1997 году Джошуа Блохом) это был прекрасный выбор, но сегодня мы можем добиться большего.

С 2003 года сортировка списков Python использует алгоритм, известный как timsort (в честь Тима Петерса, который его написал). Это стабильная, адаптивная, итеративная сортировка слиянием, которая требует гораздо меньше, чем n log (n) сравнений при работе с частично отсортированными массивами, при этом предлагая производительность, сопоставимую с традиционной сортировкой слиянием при запуске на случайных массивах. Как и все правильные слияния, timsort стабилен и работает за время O (n log n) (худший случай). В худшем случае timsort требует временного пространства для хранения n / 2 ссылок на объекты; в лучшем случае для этого потребуется лишь небольшое постоянное пространство. Сравните это с текущей реализацией, которая всегда требует дополнительного места для n ссылок на объекты и превосходит n log n только в почти отсортированных списках.

Timsort подробно описан здесь: http://svn.python.org/projects/python/trunk/Objects/listsort.txt .

Первоначальная реализация Тима Петерса написана на C. Джошуа Блох портировал ее с C на Java, а затем тщательно протестировал, протестировал и настроил полученный код. Полученный код является заменой для java.util.Arrays.sort. На высокоупорядоченных данных этот код может работать до 25 раз быстрее, чем текущая реализация (на виртуальной машине сервера HotSpot). На случайных данных скорости старой и новой реализации сопоставимы. Для очень коротких списков новая реализация значительно быстрее старой даже для случайных данных (поскольку позволяет избежать ненужного копирования данных).

Также см. Использует ли Java 7 Tim Sort для Method Arrays.Sort? .

Не существует единственного «лучшего» выбора. Как и во многих других вещах, речь идет о компромиссах.