Sortowanie zajmuje O (n log n) w przypadku szeregowym. Jeśli mamy O (n) procesorów, liczylibyśmy na liniowe przyspieszenie. Istnieją algorytmy równoległe O (log n), ale mają one bardzo wysoką stałą. Nie mają również zastosowania na standardowym sprzęcie, który nie ma w pobliżu procesorów O (n). W przypadku procesorów p rozsądne algorytmy powinny zająć O (n / p log n) czasu.
W przypadku seryjnego sortowanie szybkie ma średnio największą złożoność w czasie wykonywania. Równoległy algorytm szybkiego sortowania jest łatwy do zaimplementowania (patrz tutaj i tutaj ). Jednak nie działa dobrze, ponieważ pierwszym krokiem jest podzielenie całej kolekcji na jeden rdzeń. Znalazłem informacje o wielu algorytmach sortowania równoległego, ale jak dotąd nie widziałem niczego, co wskazywałoby na wyraźnego zwycięzcę.
Chcę posortować listy od 1 miliona do 100 milionów elementów w języku JVM działającym na 8 do 32 rdzeniach.