Dlaczego Collections.sort używa Mergesort, a Arrays.sort nie?

Używam JDK-8 (x64). W przypadku Arrays.sort(prymitywów) w dokumentacji Java znalazłem:

Algorytm sortowania to Dual-Pivot Quicksort autorstwa Vladimira Yaroslavskiya, Jona Bentleya i Joshua Blocha. "

Dla Collections.sort(obiektów) znalazłem to „Timsort”:

Ta implementacja jest stabilnym, adaptacyjnym, iteracyjnym łączeniem ... Ta implementacja zrzuca określoną listę do tablicy, sortuje tablicę i wykonuje iterację po liście resetując każdy element z odpowiedniej pozycji w tablicy.

Jeśli Collections.sortużywa tablicy, dlaczego po prostu nie wywołuje Arrays.sortlub nie używa funkcji QuickSort z dwoma obrotami ? Dlaczego warto korzystać z Mergesort ?

API gwarantuje stabilne sortowanie, którego nie oferuje Quicksort . Jednak podczas sortowania wartości pierwotnych według ich naturalnej kolejności nie zauważysz różnicy, ponieważ wartości pierwotne nie mają tożsamości. Dlatego też Quicksort może być używany dla tablic pierwotnych i będzie używany, gdy zostanie uznany za bardziej wydajny¹ .

W przypadku obiektów można zauważyć, że obiekty o różnej tożsamości, które są uważane za równe w zależności od ich equalswykonania lub dostarczonej Comparatorzmiany, zmieniają kolejność. Dlatego Quicksort nie wchodzi w grę. Tak więc używany jest wariant MergeSort , obecne wersje Java używają TimSort . Dotyczy to obu Arrays.sorti Collections.sortchociaż w Javie 8 Listsamo w sobie może przesłonić algorytmy sortowania.

¹ Zaletą wydajności Quicksort jest to, że wymaga mniej pamięci, gdy jest wykonywana na miejscu. Ale ma dramatyczną wydajność w najgorszym przypadku i nie może wykorzystywać serii wstępnie posortowanych danych w tablicy, co robi TimSort .

Dlatego algorytmy sortowania zostały przerobione z wersji na wersję, pozostając w myląco nazwanej klasie DualPivotQuicksort. Ponadto dokumentacja nie nadrobiła zaległości, co pokazuje, że generalnie złym pomysłem jest nazwanie w specyfikacji algorytmu używanego wewnętrznie, gdy nie jest to konieczne.

Obecna sytuacja (w tym Java 8 do Java 11) przedstawia się następująco:

• Ogólnie rzecz biorąc, metody sortowania tablic prymitywnych używają funkcji Quicksort tylko w określonych okolicznościach. W przypadku większych tablic będą najpierw próbować zidentyfikować serie wstępnie posortowanych danych, tak jak robi to TimSort , i scalą je, gdy liczba przebiegów nie przekroczy określonego progu. W przeciwnym razie powrócą do Quicksort , ale z implementacją, która powróci do sortowania przez wstawianie dla małych zakresów, co ma wpływ nie tylko na małe tablice, ale także na rekursję szybkiego sortowania.
• sort(char[],…)i sort(short[],…)dodaj kolejny przypadek specjalny, aby użyć sortowania zliczającego dla tablic, których długość przekracza określony próg
• Podobnie, sort(byte[],…)użyje sortowania zliczającego , ale ze znacznie mniejszym progiem, co tworzy największy kontrast w stosunku do dokumentacji, ponieważ sort(byte[],…)nigdy nie używa Quicksort. Używa sortowania przez wstawianie tylko dla małych tablic i sortowania zliczania w przeciwnym razie.

Nie znam dokumentacji, ale implementacja java.util.Collections#sortw Javie 8 (HotSpot) wygląda tak:

@SuppressWarnings({"unchecked", "rawtypes"})
public static <T> void sort(List<T> list, Comparator<? super T> c) {
    list.sort(c);
}

I List#sortma tę implementację:

@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

W końcu Collections#sort używa Arrays#sort(elementów obiektów) za kulisami. Ta implementacja używa sortowania przez scalanie lub sortowania według czasu.

Według Javadoc tylko prymitywne tablice są sortowane za pomocą Quicksort. Tablice obiektów są również sortowane za pomocą Mergesort.

Wydaje się więc, że Collections.sort używa tego samego algorytmu sortowania, co Arrays.sort dla obiektów.

Innym pytaniem byłoby, dlaczego inny algorytm sortowania jest używany dla tablic pierwotnych niż dla tablic Object?

Jak stwierdzono w wielu odpowiedziach.

Funkcja Quicksort jest używana przez Arrays.sort do sortowania kolekcji pierwotnych, ponieważ stabilność nie jest wymagana (nie będziesz wiedzieć lub przejmować się tym, czy podczas sortowania zamieniono dwa identyczne liczby całkowite)

MergeSort, a dokładniej Timsort, jest używany przez Arrays.sort do sortowania kolekcji obiektów. Wymagana jest stabilność. Quicksort nie zapewnia stabilności, Timsort tak.

Collections.sort deleguje do Arrays.sort, dlatego widzisz javadoc odwołujący się do MergeSort.

Szybkie sortowanie ma dwie główne wady, jeśli chodzi o sortowanie przez scalanie:

• Nie jest stabilny, jeśli chodzi o nieprymitywne.
• Nie gwarantuje wydajności n log n.

Stabilność nie jest problemem dla typów pierwotnych, ponieważ nie istnieje pojęcie tożsamości jako odrębnej od równości (wartości).

Stabilność to poważna sprawa podczas sortowania dowolnych obiektów. Dodatkową zaletą jest to, że sortowanie przez scalanie gwarantuje wydajność n log n (czas) bez względu na dane wejściowe. Dlatego wybrano sortowanie przez scalanie, aby zapewnić stabilne sortowanie (sortowanie przez scalanie) do sortowania odniesień do obiektów.