Почему Коллекции.сортировка слиянием использует вместо сортировки быстрая сортировка? [закрытый]

весьма вероятно от Джоша Блоха §:

Я написал эти методы, так что я полагаю, что я квалифицирован, чтобы ответить. Это правда, что нет единого лучшего алгоритма сортировки. Быстрая сортировка имеет два основных недостатка по сравнению с mergesort:

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

2. Это не гарантия производительность N записей N; это может привести к квадратичной производительности патологические входы.

стабильность не является проблемой для примитивных типов, так как нет понятия идентичность в отличие от равенства (ценности). И возможность квадратичное поведение считалось не проблемой на практике для Реализация Бентли и Макилроя (или впоследствии для Двойной Поворотный Быстрая сортировка), именно поэтому эти варианты QuickSort были использованы для примитивные сорта.

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

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

и после актуальна:

алгоритм, используемый java.утиль.Матрицы.сортировать и (косвенно) по Ява.утиль.Коллекции.сортировка для сортировки ссылок на объекты-это " изменено mergesort (в котором слияние опущено, если самый высокий элемент Нижний подсписок меньше, чем самый нижний элемент в верхнем подсписке)." Он является достаточно быстрым стабильным видом, который гарантирует O (N log n) спектакль и требует o (n) дополнительного пространства. В свое время (было написано в 1997 году Джошуа блох), это был прекрасный выбор, но сегодня, но мы можем облагодетельствовать.

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

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

оригинальная реализация Тима Питерса написана в C. Joshua Bloch портировал его с C на Java и закончил тестирование, бенчмаркинг и настройку результирующий код обширно. Полученный код является выпадающим замена для Java.утиль.Матрицы.род. На сильно упорядоченных данных, это код может работать до 25 раз быстрее, чем текущая реализация (on VM сервера HotSpot). На случайных данных, скорости о старом и новом реализации сопоставимы. Для очень коротких списков, новый реализация существенно быстрее, чем старая даже на случайном данные (потому что это позволяет избежать ненужного копирования данных).

Также см. Java 7 использует сортировку Tim для массивов методов.Сорт?.

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