Java & Merge Sort

Question

Почему Java impl выбирает сортировку слияния по быстрому сортировке? и почему они копируют содержимое в массив?

API: «Алгоритм сортировки представляет собой модифицированную систему слияния (в которой слияние опущено, если наивысший элемент в нижнем подсписке меньше наименьшего элемента в высоком подсписке). Этот алгоритм предлагает гарантированный n log (n) производительность. Эта реализация выгружает указанный список в массив, сортирует массив и выполняет итерацию по списку, сбрасывая каждый элемент из соответствующей позиции в массиве. Это позволяет избежать производительности n2 log (n), которая возникла бы при попытке отсортировать связанный список на месте ".

Answer 1

Java ребята торговали наихудший сценарий с делом AVG, как вы, наверное, знаете, быстрая сортировка может работать в O (N^2) в худшем случае ..

Вы можете прочитать в API, сортировка связанного списка на месте более сложная n^2log (n)

Сортировка слияний стабильна, что не соответствует эффективной версии быстрой сортировки. (который может быть очень важно при сортировке объектов + многие программисты берут, что, как должное, когда они используют Collections.sort())

Answer 2

документация дает ответ на оба ваши вопросы:

Этот алгоритм обеспечивает гарантированную n log (n).

Merge сортировка не имеет патологические случаи сортировки

Еще одно преимущества объединения рода над быстрой сортировкой, что сортировка слияния устойчиво; quicksort обычно нестабильна. (Очевидно, что с достаточно усилий, вы можете сделать его стабильным, но я считаю, что это довольно дорого, чтобы сделать это.)

Это позволяет избежать п журнала (п) производительность , что бы в результате попытки соберите связанный список на месте.

Копирование в массив сначала означает, что вы не полагаетесь на сложность доступа исходной коллекции к отдельным элементам. Я полагаю, что может посмотреть, содержит ли список RandomAccess и сортировать на месте, если это так, но RandomAccess был введен только в 1.4.

Answer 3

• Сортировка по списанию гарантировала O (n log n) поведение. Быстрая сортировка имеет наихудшие характеристики O (n^2). Поэтому в некоторых случаях сортировка слияния выполняется быстрее, и она имеет лучшую верхнюю границу.

• Такой вид сортировки, как быстрая сортировка, не работает в связанных списках, как упоминает ваша цитата. Чтобы работать предсказуемо для всех типов коллекций, необходима копия.

• Быстрая сортировка сама по себе нестабильна. Стабильность иногда желательна, и что-то, что должны предложить API.

Answer 4

Я считаю, что основная причина, по которой была выбрана mergesort, заключается в том, что она стабильна.

n log n наихудшая гарантия, о которой говорили другие, является преимуществом, но, скорее всего, это не основная причина. Если вы посмотрите на методы Arrays.sort, все виды на примитивах используют quicksort, а сортировки по Object[] используют mergesort. Это связано с тем, что стабильный вид не имеет значения для примитивов; равные примитивы не отличаются друг от друга.