Java i .NET: Dlaczego domyślnie stosowane są różne algorytmy sortowania?

Zastanawiam się tylko, dlaczego Javai .NET Frameworkużywa domyślnie innego algorytmu sortowania.

W Javie domyślnie Array.Sort()korzysta z algorytmu scalania sortowania i jak mówi Wikipedia.com :

W Javie metody Arrays.sort () używają sortowania scalonego lub dostrajanego szybkiego sortowania w zależności od typów danych oraz do przełączania wydajności implementacji na sortowanie wstawiania, gdy sortowanych jest mniej niż siedem elementów tablicy

W .NET Framework Array.Sort/List.Sort() używa szybkiego sortowania jako domyślnego algorytmu sortowania ( MSDN ):

List.Sort () używa Array.Sort, który wykorzystuje algorytm QuickSort. Ta implementacja działa w sposób niestabilny; to znaczy, jeśli dwa elementy są równe, ich kolejność może nie zostać zachowana. Natomiast stabilny sort zachowuje porządek elementów, które są równe.

Patrząc na świetną tabelę „Porównanie algorytmów” , możemy zobaczyć, że oba algorytmy zachowują się zupełnie inaczej niż perspektywy najgorszego przypadku i wykorzystania pamięci:

Zarówno Javai .NETsą wielkie Ramki dla rozwoju rozwiązań dla przedsiębiorstw, zarówno ma platform wbudowanych rozwoju. Dlaczego więc domyślnie używają innego algorytmu sortowania, jakieś myśli?

Choć deterministyczne są same komputery, inżynieria komputerowa nie jest nauką ścisłą. Dwie osoby, mając tę ​​samą dziedzinę problemów, przeprowadzą analizę i opracują dwa różne rozwiązania, które spełniają wszystkie ograniczenia problemu. Empiryczne określenie, która z nich jest „lepsza” w ogólnym przypadku, może być trudne lub niemożliwe.

Domyślam się, że .NET QuickSort jest nałożony na coś w MFC lub Windows API i prawdopodobnie jest odziedziczony z dużo starszych wersji Windows, gdzie wielowątkowa przewaga MergeSort nie byłaby brana pod uwagę nawet na komputerach dzień. ( EDYCJA: nie jest, chociaż programiści Microsoft byli fanboyami QuickSort od dawna, o czym świadczy ten wybór implementacji sortowania od MS-DOS).

Java, która nie może korzystać z żadnej implementacji specyficznej dla platformy, ponieważ Java została zaprojektowana od zera, aby była całkowicie niezależna od platformy, poszła inną drogą. Kto wie, dlaczego MergeSort wyszedł na górę; zgaduję, że implementacja wygrała konkurencję wydajnościową z innymi rodzajami, które wymyślili programiści, albo że MergeSort z przestrzenią O (n) wyglądał najlepiej na papierze pod względem wydajności w najlepszym i najgorszym przypadku (MergeSort nie ma pięty Achillesa związanej z wyborem elementów, takim jak QuickSort, a najlepszym jej przykładem jest lista prawie posortowana, chociaż często jest to najgorsza opcja QuickSort). Wątpię, czy początkowo rozważano korzyści z wielowątkowości, ale obecne wdrożenie może być wielowątkowe.

Różne zespoły projektowe w dwóch różnych firmach doszły do ​​różnych wniosków dotyczących zwykłego przypadku użycia swoich ram i komponentów i postanowiły je odpowiednio wdrożyć.

Zasadniczo każda firma dokonała analizy, przeanalizowała bazę klientów i podjęła odpowiednie decyzje.

Nie można oczekiwać, że analizy przeprowadzane przez różne firmy i zespoły przy użyciu różnych założeń i surowych danych doprowadzą do tego samego wniosku.

To pytanie jest nieco nieaktualne, ponieważ Java używa teraz Timsort (od Java 7)

Z wymienionych wymienionych algorytmów:

• Quicksort ma niekorzystną wydajność w najgorszym przypadku przy O (n ^ 2), ale jest nieco lżejszy / zajmuje mniej pamięci, więc oferuje lepszą wydajność w typowym przypadku.

• Mergesort ma gwarantowaną najgorszą wydajność przy O (n log n), ale przenosi nieco więcej kosztów ogólnych i wymagań dotyczących pamięci. Jest również automatycznie stabilny (tzn. Utrzymuje równe elementy w tej samej kolejności).

Projektanci Java wydają się być nieco bardziej konserwatywni / skoncentrowani na „właściwej rzeczy”, więc nie jest zaskoczeniem, że wybrali Mergesort z dwóch, ponieważ oferuje lepsze gwarancje.

Nie masz pewności, dlaczego Microsoft wybrał Quicksort, a może myśleli, że dzięki temu będą wyglądać lepiej w niektórych mikro-testach?