Сортировка в Java

Прочел в документации и нигде не нашел объяснения (гуглил без результата), почем
для реализации сортировки выбран метод слияния (пишут модифицированный, а что именно модифицировано ?), а не Qsort ? 

Только из-за устойчивости алгоритма слияния или какие-то особенности работы с памятью в реализации JVM обуславливают этот выбор ?

Ведь Qsort требует значительно меньше дополнительной памяти да и по скорости (при разумной реализации) почти всегда превосходит (если верить Кнуту) MergeSort.

Какие есть соображения на эту тему ?

UPD

Ответов больше нет, обсуждение закончено. Всем огромное спасибо.

Просмотр материалов по MergeSort в Wiki навел меня на мысль попробовать реализоват
ее (невзирая на предупреждение в Вики о большой сложности алгоритма) без выделения дополнительной памяти размером  O(n).



yozh, одна реализация (или минимум реализаций) это мне тоже приходило в голову. Хотелось бы узнать, так ли это на самом деле.

Nikolay Artamonov, а какие еще устойчивые сложностью n*log(n) есть ?  Я сходу н
припоминаю. 

Тогда уж еще один вопрос, почему не дали выбирать из нескольких (устойчивая/неустойчивая
? Я имею в виду наличие нескольких алгоритмов в стандартных пакетах. Возможно, что бы путаницы меньше было. И так в Java огромное количество классов-методов.

1) Спасибо за ссылку, буду смотреть (это к комментарию с ссылкой на http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms)

2) Нашел там интересный линк на реализацию в jdk7 - http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79
Обещают замечательные характеристики (по дополнительной памяти max n/2 !) и вообще интересно.
    

Ответы

Ответ 1

В стандартной библиотеке Java существует три группы перегруженных методов для сортировки:


java.util.Arrays.sort(prim[], ...) — для сортировки массивов примитивов prim (int, byte, char, и т.д.). Использует алгоритм быстрой сортировки (quick sort).
java.util.Arrays.sort(T[], ...) и java.util.Arrays.sort(Object[], ...) — для сортировк
массивов комплексных объектов произвольного типа T или Object. Использует алгоритм сортировки слиянием (merge sort).
java.util.Collections.sort() — для сортировки коллекций. Использует алгоритм сортировки слиянием (merge sort).


Причина, по которой для сортировки коллекций и массивов комплексных объектов выбра
алгоритм сортировки слиянием, заключается в том, что данный алгоритм является устойчиво
сортировкой, в отличие от быстрой сортировки, являющейся неустойчивой. Устойчивой сортировкой называется такой алгоритм, который сохраняет порядок следования элементов с одинаковыми ключами сортировки. К примеру, пусть нам требуется отсортировать следующие пары чисел по первому числу пары:

(4, 2)  (3, 7)  (3, 1)  (5, 6)


Тогда на выходе, в зависимости от использованного алгоритма сортировки, мы може
получить два различных результата:

(3, 7)  (3, 1)  (4, 2)  (5, 6)   (порядок сохранен)
(3, 1)  (3, 7)  (4, 2)  (5, 6)   (порядок изменен)


В первом случае пары (3, 7) и (3, 1) с равными ключами сортировки остались в то
же порядке следования, как и изначально. Во втором случае они поменялись местами.

Почему важна устойчивая сортировка? Она позволяет производить цепочку последовательны
сортировок, добиваясь сортировки в группах и подгруппах коллекции. Покажем, что эт
означает, на примере (примеры записаны на языке Scala для минимизации избыточного кода, присущего Java, но смысл будет ясен). Пусть мы имеем структуру данных для представления музыкальных записей:

// `albumName` - имя музыкального альбома;
// `trackNumber` - номер трека в альбоме.
case class Record(albumName: String, trackNumber: Int)


Разместим в списке несколько музыкальных произведений (из дискографии группы Metallica) в произвольном порядке:

val records = List(Record("Master of Puppets", 7), Record("Load", 4),
                   Record("Load", 2), Record("Reload", 5),
                   Record("Load", 3), Record("Reload", 3))


Теперь отсортируем записи по номеру трека:

scala> val byTrackNumber = records.sortBy(_.trackNumber)
byTrackNumber: List[Record] = List(Record(Load,2), Record(Load,3), Record(Reload,3), Record(Load,4), Record(Reload,5), Record(Master of Puppets,7))


А затем отсортируем еще раз, но уже по имени альбома:

scala> byTrackNumber.sortBy(_.albumName)
res4: List[Record] = List(Record(Load,2), Record(Load,3), Record(Load,4), Record(Master of Puppets,7), Record(Reload,3), Record(Reload,5))


Что мы получили? Мы получили список записей, отсортированный по имени альбома, 
в каждом альбоме отсортированный по номеру трека! Для этого мы сначала применили сортировк
по менее значимому ключу (номер трека), которая сортирует для нас записи в подгруппа
(альбомах). Затем сортировку по более значимому ключу - имени альбома. Такая последовательност
важна. Следует заметить, что этот результат можно было бы получить, если сразу отсортировать записи по альбому И номеру трека за один раз, но существуют ситуации, когда нам неизвестны заранее все ключи, по которым мы будем сортировать коллекцию. К примеру, пользователь программы может выбрать в графическом интерфейсе сначала сортировку по полю "номер трека", а только затем по полю "альбом".

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


Ответ 2

Сортировка методом слияния используется для массивов (и списков, так как в конечно
итоге перед сортировкой списки перегоняются в массивы) объектов. Для сортировки примитиво
используется быстрая сортировка. Из этого можно сделать вывод, что дело именно в устойчивости алгоритма: для примитивов она не имеет значения, так как никакой разницы между двумя, скажем, тройками типа int нет; в то же время a.compareTo(b) == 0 не означает, что a == b.


Ответ 3

Быстрая сортировка неэффективна на упорядоченных массивах(иногда даже переполняет стек вызовов), а MergeSort этого недостатка лишена. Хотя, если верить википедии:

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


Ответ 4

Разница в производительности. В лучшем случае сортировка слиянием эффективнее быстрой сортировки. Правда разница в коэффициенте, а не то чтобы очень огромная.


Ответ 5

В худшем случае qSort работает за O(n^2), то есть гораздо медленнее, чем в среднем. Merge этим не страдает.
Для объектов, когда операция сравнения становится более весомой (Comparable.compareTo() или Comparator.compare()), это особенно актуально.


Ответ 6

Рандомизированный QSort работает всегда за O(n log n). У этого есть вполне строгое доказательство.
А в Java реализована как сортировка именно QSort (с небольшой модификацией: выбираютс
не один, а два опорных элемента, и массив делится на три части). Вот пример: http://download.oracle.com/javase/1.4.2/docs/api/java/util/Arrays.html#sort(byte[])