Sortowanie przez łączenie naturalne

Sortowanie przez łączenie naturalne jest zaliczane do grupy sortowań zewnętrznych, tzn. operuje na taśmach. Taśmą możemy nazwać dowolny plik o dostępie sekwencyjnym (tzn. w danym momencie dostępny jest tylko jeden element takiego pliku), niemożliwe jest więc wykorzystywanie tradycyjnych metod sortowania. W wypadku plików o dostępie sekwencyjnym czasy dostępu do określonej pozycji są zbyt duże, aby można było sortować je "w miejscu" - czyli bezpośrednio na nośniku. Niesekwencyjny dostęp do sortowanego pliku ograniczałby również funkcjonalność buforów zapewniających szybszy dostęp do danych. Głównym zastosowaniem sortowań zewnętrznych jest porządkowanie danych nie mogących zmieścić się w pamięci operacyjnej, przy zachowaniu wymogu sekwencyjnego dostępu do pliku. Sortowanie przez łączenie, które zawsze scala dwa najdłuższe podciągi posortowane nazywa się sortowaniem przez łączenie naturalne. Wykorzystywany jest fakt, że w plikach znajdują się dane częściowo posortowane (serie) - scalenie serii a o długości m i serii b o długości n w serię c o długości m+n jest dużo wydajniejsze od ich sortowania.Występują dwie fazy: dzielenia (dzielimy taśmę na dwie taśmy pomocnicze) i łączenia (scalamy taśmy pomocnicze). Przebiegiem nazywamy te dwie fazy występujące po sobie. Przykładowy zbiór danych: 1 5 2 3 8 10 4 2 7 5 8 9 1 i serie w nim, wyróżnione znakiem "|": 1 5 | 2 3 8 10 | 4 | 2 7 | 5 8 9 | 1 W sortowaniu takim wykorzystuje się 3 taśmy.W dalszym opisie przyjęto, że c to taśma danych, zaś a i b to taśmy pomocnicze.