Java и сортировка слиянием

Question

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

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

Answer 1

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

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

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

Answer 2

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

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

Сортировка слиянием не имеет патологическихслучаи быстрой сортировки

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

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

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

Answer 3

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

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

Answer 4

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

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

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