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.

Algorytm postępowania

1. Kopiujemy dane z pliku źródłowego do taśmy c.

faza dzielenia:

2. Szukamy serii i kopiujemy je na przemian do taśmy a oraz b - po tej operacji w taśmach powinna się znajdować równa liczba serii (ale zwykle tak nie jest - patrz uwagi)

faza łączenia:

3. Bierzemy po jednej serii z każdej z taśm (a i b) i scalamy je do taśmy c

4. Powtarzamy punkt 3 tak długo, aż serie w którejś z taśm się skończą - najlepszy przypadek to taki, w którym udało się doprowadzić do wyczerpania serii w tym samym czasie. Jeśli w którejś z taśm jeszcze są serie, kopiujemy to co zostało na koniec taśmy c

5. Powtarzamy punkty 2-4 do momentu, gdy w taśmie c będzie tylko jedna seria

przepisanie danych:

6. Kopiujemy zawartość taśmy c do pliku wynikowego

Uwagi

Podczas wykonywania punktu 3 może się zdarzyć, że serie w taśmach pomocniczych się połączą, wtedy jest jedna seria mniej

| - podział serii ? - ten podział serii zniknął w wyniku podziału taśmy

dane: 1 5 6 2 20 8 9 1 5

c: 1 5 6 | 2 20 | 8 9 | 1 5

po fazie dzielenia mamy

a: 1 5 6 ? 8 9

b: 2 20 | 1 5

Nieparzysta liczba serii nie podzieli się równo na 2. Walczyć z tym można pisząc odpowiednie procedury dzielące (tzn. tworzące dodatkowe serie).