Dlaczego Collections.sort używa sortowania przez scalanie zamiast szybkiego sortowania?

Wiemy, że szybkie sortowanie to najszybszy algorytm sortowania.

JDK6 collections.sortużywa algorytmu sortowania przez scalanie zamiast sortowania szybkiego. Ale Arrays.sort używa algorytmu szybkiego sortowania.

Jaki jest powód, dla którego Collections.sort używa sortowania przez scalanie zamiast szybkiego sortowania?

Bardzo prawdopodobne od Josha Blocha § :

Napisałem te metody, więc przypuszczam, że mam kwalifikacje do udzielenia odpowiedzi. Prawdą jest, że nie ma jednego najlepszego algorytmu sortowania. QuickSort ma dwie główne wady w porównaniu z połączeniem:

1. Nie jest stabilny (jak zauważył parsifal).

2. Nie gwarantuje wydajności n log n; może obniżyć się do kwadratowej wydajności na patologicznych bodźcach.

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). Uznano, że możliwość zachowania kwadratowego nie stanowi problemu w praktyce dla implementacji Bentely i McIlroy (lub później dla Dual Pivot Quicksort ), dlatego te warianty QuickSort zostały użyte do sortowania pierwotnego.

Stabilność to poważna sprawa podczas sortowania dowolnych obiektów. Załóżmy na przykład, że masz obiekty reprezentujące wiadomości e-mail i sortujesz je najpierw według daty, a następnie według nadawcy. Oczekujesz, że będą sortowane według daty w każdym nadawcy, ale będzie to prawdą tylko wtedy, gdy sortowanie będzie stabilne. Dlatego zdecydowaliśmy się zapewnić stabilne sortowanie (sortowanie przez scalanie) do sortowania odniesień do obiektów. (Technicznie rzecz biorąc, wielokrotne sekwencyjne sortowanie stabilne skutkuje uporządkowaniem leksykograficznym na klawiszach w odwrotnej kolejności sortowania: sortowanie końcowe określa najbardziej znaczący podklucz).

Dodatkową zaletą jest to, że sortowanie przez scalanie gwarantuje wydajność n log n (czas) niezależnie od danych wejściowych. Oczywiście ma swoją wadę: szybkie sortowanie jest sortowaniem „na miejscu”: wymaga tylko log n zewnętrznej przestrzeni (aby utrzymać stos wywołań). Z drugiej strony scalanie, sortowanie wymaga O (n) przestrzeni zewnętrznej. Wariant TimSort (wprowadzony w Javie SE 6) wymaga znacznie mniej miejsca (O (k)), jeśli tablica wejściowa jest prawie posortowana.

Istotne są również następujące kwestie:

Algorytm używany przez java.util.Arrays.sort i (pośrednio) przez java.util.Collections.sort do sortowania odniesień do obiektów to „zmodyfikowane scalanie (w którym scalanie jest pomijane, jeśli najwyższy element na niskiej podliście jest mniejszy niż najniższy element na najwyższej podliście). ” Jest to dość szybki, stabilny sort, który gwarantuje wydajność O (n log n) i wymaga O (n) dodatkowej przestrzeni. W tamtych czasach (napisany w 1997 roku przez Joshuę Blocha) był to dobry wybór, ale dziś możemy zrobić znacznie lepiej.

Od 2003 roku sortowanie list w Pythonie używa algorytmu znanego jako timsort (od nazwiska Tima Petersa, który go napisał). Jest to stabilny, adaptacyjny, iteracyjny scalanie, które wymaga znacznie mniej niż n log (n) porównań, gdy działa na częściowo posortowanych tablicach, a jednocześnie oferuje wydajność porównywalną do tradycyjnego scalania, gdy jest uruchamiany na losowych tablicach. Podobnie jak wszystkie właściwe metody scalania, sortowanie czasu jest stabilne i działa w czasie O (n log n) (najgorszy przypadek). W najgorszym przypadku sortowanie czasu wymaga tymczasowej przestrzeni do przechowywania n / 2 odniesień do obiektów; w najlepszym przypadku wymaga tylko niewielkiej stałej ilości miejsca. Porównaj to z obecną implementacją, która zawsze wymaga dodatkowego miejsca na n odniesień do obiektów i bije n log n tylko na prawie posortowanych listach.

Timsort jest szczegółowo opisany tutaj: http://svn.python.org/projects/python/trunk/Objects/listsort.txt .

Oryginalna implementacja Tima Petersa została napisana w C. Joshua Bloch przeniósł ją z języka C na Javę, a następnie przetestował, przetestował i dostroił wynikowy kod. Powstały kod jest zastępczym zamiennikiem dla java.util.Arrays.sort. Na wysoce uporządkowanych danych ten kod może działać do 25 razy szybciej niż bieżąca implementacja (na maszynie wirtualnej serwera HotSpot). W przypadku danych losowych prędkości starych i nowych implementacji są porównywalne. W przypadku bardzo krótkich list nowa implementacja jest znacznie szybsza niż stara, nawet w przypadku danych losowych (ponieważ pozwala uniknąć niepotrzebnego kopiowania danych).

Zobacz też Czy Java 7 używa Tim Sort dla Method Arrays.Sort?.

Nie ma jednego „najlepszego” wyboru. Podobnie jak w przypadku wielu innych rzeczy, chodzi o kompromisy.