Sortowanie przez łączenie proste
Z Wikipedii
Sortowanie przez łączenie proste to metoda ekstensywna o zapotrzebowaniu na dodatkową pamięć równą pojemności tablicy posortowanej. Wydajnościowo bliska quicksort, statystycznie z nim przegrywa, dobra metoda dla sortowania zewnętrznego (plików).
Algorytm mergesort:
- dla tablic: podziel tablice na odcinki jednoelementowe, scalaj element 1 z 2, 3 z 4 itd., umieszczając wynik w drugiej tablicy. Potem 2-elementowe odcinki scalaj w 4-elementowe (wersja podstawowa iteracyjna).
Analogicznie postępujemy dla plików, stosuje się dwa pliki wejściowe i jeden wyjściowy.
