Stronę tą wyświetlono już: 4130 razy
Sortowanie przez scalanie to typowy przykład algorytmu rekurencyjnego, w którym konieczny jest podział danych wejściowych na podgałęzie o rozmiarze danych nie większym niż 2. Innymi słowy (tak jak pokazane zostało to na rysunku poniżej) dla przykładowych danych: 2, 6, 3, 7, 5, 4, 1, 8 wykonuje się podział na dwa podzbiory: 2, 6, 3, 7 i 5, 4, 1, 8 a następnie pierwszy zbiór znów jest dzielony na pół i po uzyskaniu zbiorów o liczebności ≤ 2 sortuje się je. Dane powracają do głównej gałęzi programu i po posortowaniu drugiej jej części są łączone z równoczesnym ich sortowaniem.
Wadą tego algorytmu jest konieczność użycia pamięci co przy zbyt dużej liczbie podgałęzi może mieć nieprzyjemne skutki. Rozwiązaniem może być dzielenie danych na mniejsze partie i ich odpowiednie sortowania na najniższych gałęziach dowolnym znanym algorytmem sortowania. Przykładowa animacja działania algorytmu dla 50 losowo wygenerowanych wartości widoczna jest poniżej.
- czerwony - partia danych sortowanych;
- niebieski - partia wydzielonych danych (gałąź danych);
- zielony - pozostałe elementy tablicy
Szacunkowa złożoność czasowa tego algorytmu wynosi n · log2 n. Istnieje również wersja ulepszona pomijająca rekurencję poprzez zabranie się zna realizację algorytmu od drugiej strony w sposób iteracyjny, czyli dane wejściowe najpierw są dzielone na porcje o liczebności równej co najwyżej 2 a następnie sortowana i łączone w zbiory o liczebności nie większej niż 4 itd. z wykorzystaniem pętli.
Algorytm z powyższej animacji zapisany w JavaScript można zapisać w następujący sposób: