Nie byłem w stanie znaleźć żadnej dyskusji, która mówi, że jedna metoda mergesort powinna być szybsza od drugiej.
Sortowniki typu bottom-up i top-down, a także inne warianty zostały dobrze przebadane w latach 90. Krótko mówiąc, jeśli mierzysz koszt jako liczbę porównań poszczególnych kluczy, najlepsze koszty są takie same (~ (n lg n)/2), najgorszy koszt odgórnego jest niższy lub równy najgorszemu przypadek oddolnego (ale oba ~ n lg n) i średni koszt odgórny jest mniejszy lub równy średniemu przypadkowi oddolnemu (ale obydwu ng n), gdzie "lg n" jest logarytm binarny. Różnice wynikają z terminów liniowych. Oczywiście, jeśli n = 2^p, te dwa warianty są w rzeczywistości dokładnie takie same. Oznacza to, że w ujęciu porównawczym odgórne jest zawsze lepsze niż oddolne. Ponadto udowodniono, że strategia podziału na połówki "połowy na pół" top-down merge sort jest optymalna. Prace badawcze pochodzą z Flajolet, Golin, Panny, Prodinger, Chen, Hwang i Sedgewick.
Oto co wymyśliłem w mojej książce projektowania i analizy programów czysto funkcjonalne (College Publications, Wielka Brytania), w Erlang:
tms([X|T=[_|U]]) -> cutr([X],T,U);
tms(T) -> T.
cutr(S,[Y|T],[_,_|U]) -> cutr([Y|S],T,U);
cutr(S, T, U) -> mrg(tms(S),tms(T)).
mrg( [], T) -> T;
mrg( S, []) -> S;
mrg(S=[X|_],[Y|T]) when X > Y -> [Y|mrg(S,T)];
mrg( [X|S], T) -> [X|mrg(S,T)].
pamiętać, że jest nie stabilny porządek. Ponadto, w Erlang (i OCaml), musisz użyć aliasów (ALIAS = ...) we wzorach, jeśli chcesz zaoszczędzić pamięć. Sztuczka polega na znalezieniu środka listy bez znajomości jej długości. Odbywa się to za pomocą cutr/3, który obsługuje dwa wskaźniki do listy wejściowej: jeden jest zwiększany o jeden, a drugi o dwa, więc gdy drugi osiągnie koniec, pierwszy znajduje się pośrodku. (Nauczyłem się tego z pracy Oliviera Danvy'ego.) W ten sposób nie musisz śledzić długości i nie duplikujesz komórek drugiej połówki listy, więc potrzebujesz tylko (1/2) n lg n dodatkowej przestrzeni, w przeciwieństwie do n lg n . Nie jest to dobrze znane.
Często twierdzi się, że wariant "od dołu do góry" jest preferowany w przypadku języków funkcjonalnych lub listy połączonej (Knuth, Panny, Prodinger), ale nie sądzę, aby było to prawdą.
byłem zaskoczony jak ty brakiem dyskusji na temat rodzaju łączenia, więc zrobiłem moje własne badania i napisał dużą rozdział o nim. Obecnie przygotowuję nowe wydanie z większą ilością materiałów na temat sortowania seryjnego.
Nawiasem mówiąc, istnieją inne warianty: kolejka seryjnej sortowania i scalania na linii sortowania (I omówić ostatnie w mojej książce).
[EDIT: Ponieważ miarą kosztu jest liczba porównań, nie ma różnicy między wyborze tablicę porównaniu połączonej listy. Oczywiście, jeśli zaimplementujesz wariant od góry do dołu z połączonymi listami, musisz być sprytny, ponieważ niekoniecznie znasz liczbę kluczy, ale musisz przejść przez co najmniej połowę kluczy za każdym razem i realokacja, w sumie (1/2) n lg n komórek (jeśli jesteś sprytny). Sortowanie typu "od dołu do góry" z połączonymi listami wymaga w rzeczywistości więcej dodatkowej pamięci, n lg n + n komórek. Tak więc, nawet z połączonymi listami, wariant zstępujący jest najlepszym wyborem. Jeśli chodzi o długość programu, przebieg może się różnić, ale w języku funkcjonalnym sortowanie z góry do dołu może być krótsze niż z dołu do góry, jeśli stabilność nie jest wymagana. Istnieją pewne dokumenty, które omawiają zagadnienia wdrożeń scalania rodzaju, jak na miejscu (za które trzeba tablice) lub stabilności itd Na przykład, skrupulatny Analiza mergesort Programów przez Katajainen i Larsson traff (1997)].
Porównania i zamiany są kluczowymi pozycjami kosztowymi w analizie sortowania, jestem prawie pewien. – Pointy
@Pointy tak, zwykle byłyby to pozycje do analizy przy porównywaniu różnych algorytmów sortowania. Ale w tym przypadku powinny być takie same ... to ten sam algorytm, więc nie o to mi chodzi. Moja implementacja odzwierciedla to, co jest w książce ... czy to możliwe, że od dołu do góry używa mniejszej liczby pętli ponad/przez tablicę, ale ma taką samą liczbę porównań/ruchów? – arthurakay
@NiklasB. Rozumiem twój punkt widzenia ... ale te nie przyczyniają się do rozbieżności w mojej liczbie iteracji. Jeśli spojrzysz na mój kod, śledzę tylko iteracje wewnątrz pętli rekurencyjnych/iteracyjnych. Math.floor() nie ma z tym nic wspólnego - nie używam analizy opartej na czasie – arthurakay