Можно создать дубликат:
Why java Arrays use two different sort algorithms for different types?Java: Arrays.sort QuickSort и слияние
Так что я читал Массивы doc на различных реализациях сортировки. Я заметил, что некоторые из реализаций использовали настроенную quicksort, в то время как другие использовали модифицированную систему слияния. Почему расхождение?
Спасибо!
Quicksort используется для массивов примитивных типов, в то время как mergesort для Object [] массивов.
Основная причина, почему слияние используются для объектов, которые слияние является стабильным - он не переставляет элементы, которые равны: http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
Для примитивов стабильность сортировки не имеет смысл, так как вы не можете различать два значения, равны. Следовательно, используется quicksort (кроме случаев сортировки массива объектов, для которых выполняется слияние). Более того, quicksort можно сделать на месте, поэтому нет необходимости выделять другой массив.
В сегодняшнем мире mergesort стал доминирующим сортировщиком, поскольку он может быть реализован для использования нескольких ядер – ControlAltDel
, но JDK пока не использует это. –
Тем не менее, JDK 7 больше не использует mergesort - он использует мифический [TimSort] (http://en.wikipedia.org/wiki/Timsort)! –
отмечено, спасибо майкл! – OckhamsRazor