Dziel i zwyciężaj. Sortowanie przez scalanie.
Metoda  dziel i zwyciężaj (ang. divide and conquer) służy do
Algorytm  sortowanie przez scalanie (ang. merge sort) sortuje
konstruowania algorytmów rekurencyjnych, to znaczy takich, które
ciąg elementów metodą  dziel i zwyciężaj .
wywołują same siebie. Polega ona na powtarzaniu następującego
schematu:
Dziel: Dzielimy n-elementowy ciąg na dwa podciągi po n/2
elementów każdy.
Dziel: Dzielimy problem na mniejsze podproblemy, podobne do
początkowego problemu.
Zwyciężaj: Sortujemy otrzymane podciągi, używając rekurencyjnie
sortowania przez scalanie.
Zwyciężaj: Rozwiązujemy podproblemy rekurencyjnie, chyba że są
one małego rozmiaru i dają się łatwo rozwiązać bezpośrednio, bez
Połącz: A
ączymy posortowane podciągi w jeden posortowany ciąg.
stosowania rekursji.
Gdy ciąg przeznaczony do sortowania ma długość 1, to nie
Połącz: A
ączymy rozwiązania podproblemów, alby otrzymać
używamy do niego rekursji, bo już jest posortowany.
rozwiązanie całego problemu.
Scalanie.
MERGE(A, p, q, r)
1. begin
2. n1 := q - p + 1; //długość podtablicy A[p..q]
3. n2 := r - q; //długość podtablicy A[q + 1..r]
Podstawowa operacją algorytmu sortowania przez scalanie jest
4. for i := 1 to n1 do
scalanie dwóch posortowanych ciągów, dokonywane w kroku
5. L[i] := A[p - 1 + i];
 połącz . Do scalania wykorzystamy pomocniczą procedurę
6. for j := 1 to n2 do
MERGE(A, p, q, r), gdzie A jest tablicą, a p, q, r indeksami takimi,
7. R[j] := A[q + j];
że p d" q < r, przy czym zakładamy, że podtablice A[p..q] oraz
8. L[n1 + 1] := ";
A[q + 1..r] są posortowane. Procedura MERGE scala te podtablice
9. R[n2 + 1] := ";
w jedną posortowaną podtablicę A[p..r].
10. i := 1;
Podtablice A[p..q] i A[q + 1..r] zostają skopiowane do tablic
11. j := 1;
pomocniczych L i R ( lewa i  prawa ). Na końcu każdej z tablic
12. for k := p to r do
L i R jest umieszczana specjalna wartość ". Następnie elementy
13. if L[i] d" R[j]
tablic L i R są kopiowane z powrotem do A, we właściwej
14. then begin
kolejności.
15. A[k] := L[i];
16. i := i + 1;
17. end
Dowód niezmiennika.
18. else begin
19. A[k] := R[i];
Inicjowanie: Podczas pierwszego sprawdzania warunku mamy
20. j := j + 1;
k = p, i = j = 1. Podtablica A[p..k - 1] jest pusta, L[1] i R[1] są
21. end
najmniejszymi elementami swoich tablic, które nie zostały
22. end;
skopiowane z powrotem do A.
Dzięki dodaniu wartości " na końcach L i R nie musimy przed
Utrzymanie: Załóżmy, że niezmiennik jest spełniony na początku
każdym wykonaniem wiersza 13 sprawdzać, czy w obu tablicach są
iteracji pętli. Załóżmy, że L[i] d" R[j]. Wówczas L[i] jest
jeszcze elementy do porównania.
najmniejszym elementem nie skopiowanym jeszcze z powrotem do
A. Ponieważ A[p..k - 1] zawiera k - p najmniejszych elementów,
Poprawność procedury MERGE wynika z następującego
więc po skopiowaniu w wierszu 15 elementu L[i] do A[k]
niezmiennika pętli:
podtablica A[p..k] będzie zawierać k - p + 1 najmniejszych
Podczas każdego sprawdzania warunku pętli for w wierszu 12,
elementów. Zwiększenie i w wierszu 16 oraz zmiennej sterującej k
podtablica A[p..k - 1] zawiera k - p najmniejszych elementów
powoduje, że niezmiennik będzie spełniony podczas kolejnego
tablic L[1..n1 + 1] i R[1..n2 + 1], w kolejności niemalejącej; L[i] i
sprawdzania warunku w wierszu 12. Natomiast jeśli L[i] > R[j], to
R[j] są najmniejszymi elementami swoich tablic, które nie zostały
w wierszach 19 i 20 wykonane są operacje zapewniające
jeszcze skopiowane do A.
prawdziwość niezmiennika podczas kolejnego sprawdzania warunku.
Przykład.
Działanie procedury MERGE(A, 1, 3, 7) dla tablicy A[1..7]
zawierającej ciąg (2, 4, 6, 1, 2, 3, 5). Posortowane podtablice A[1..3]
Zakończenie: Warunek w wierszu 12 jest sprawdzany po raz
i A[4..7] zostają połączone w jeden posortowany ciąg.
ostatni kiedy k = r + 1 i na mocy niezmiennika podtablica A[p..r]
zawiera r - p + 1 najmniejszych elementów tablic L[1..n1 + 1] i
i j L[1..4] R[1..5] A[1..7]
R[1..n2 + 1], w kolejności niemalejącej. Tablice L i R zawierają
1 1 [2, 4, 6, "] [1, 2, 3, 5, "] [2, 4, 6, 1, 2, 3, 5]
łącznie r - p + 3 elementy, zatem wszystkie oprócz dwóch
1 2 [2, 4, 6, "] [1, 2, 3, 5, "] [1, 4, 6, 1, 2, 3, 5]
największych, zostały skopiowane do A, a te dwa największe
2 2 [2, 4, 6, "] [1, 2, 3, 5, "] [1, 2, 6, 1, 2, 3, 5]
elementy to ".
2 3 [2, 4, 6, "] [1, 2, 3, 5, "] [1, 2, 2, 1, 2, 3, 5]
2 4 [2, 4, 6, "] [1, 2, 3, 5, "] [1, 2, 2, 3, 2, 3, 5]
3 4 [2, 4, 6, "] [1, 2, 3, 5, "] [1, 2, 2, 3, 4, 3, 5]
3 5 [2, 4, 6, "] [1, 2, 3, 5, "] [1, 2, 2, 3, 4, 5, 5]
4 5 [2, 4, 6, "] [1, 2, 3, 5, "] [1, 2, 2, 3, 4, 5, 6]
Czas działania. Procedura MERGE-SORT.
Procedura MERGE-SORT sortuje elementy podtablicy A[p..r].
Jeśli p = r, to podtablica zawiera jeden element, zatem jest już
posortowana. Jeśli p < r, to dzielimy A[p..r] na dwie podtablice:
A[p..q] i A[q + 1..r] zawierające odpowiednio n/2 i n/2
elementów.
Procedura MERGE działa w czasie Ś(n), gdzie n = r - p + 1,
ponieważ:
MERGE-SORT(A,p,r)
każda z instrukcji w wierszach 2 3, 8 11 zajmuje czas stały, 1. begin
2. if p < r then
pętle for w wierszach 4 7 zajmują czas Ś(n1 + n2) = Ś(n),
3. begin
każda z n - 1 iteracji pętli for w wierszach 12 21 zajmuje
4. q := (p + r)/2
czas stały.
5. MERGE-SORT(A, p, q);
6. MERGE-SORT(A, q + 1, r);
7. MERGE(A, p, q, r);
8. end;
9. end;
Żeby posortować całą tablicę A[1..n] należy wywołać
MERGE-SORT(A, 1, n).
Przykład. Czas działania.
Niech n = r - p + 1 będzie liczbą elementów sortowanego ciągu.
Oszacujemy czas T (n) sortowania przez scalanie. Gdy n = 1, to
Działanie algorytmu sortowanie przez scalanie dla tablicy
sortowanie odbywa się w czasie stałym c0. Gdy n > 1, to czas
A = [5, 1, 3, 7, 2, 4, 2, 6]. Scalanie posortowanych ciągów jest
rozbijamy na trzy składniki:
przedstawione za pomocą strzałek i przebiega od dołu do góry.
Dziel: Wyznaczenie środka przedziału zajmuje czas stały c1.
Zwyciężaj: Rozwiązujemy rekurencyjnie dwa podproblemy, co daje
[1, 2, 2, 3, 4, 5, 6, 7]
w sumie czas T ( n/2 ) + T ( n/2 ).
[1, 3, 5, 7] [2, 2, 4, 6]
Połącz: Procedura MERGE działa w czasie d" c2n.
[1, 5] [3, 7] [2, 4] [2, 6] Zatem dla c = max{c0, c1 + c2} mamy:

[5] [1] [3] [7] [2] [4] [2] [6]
c jeśli n = 1,
T (n) d"
T ( n/2 ) + T ( n/2 ) + cn jeśli n > 1.
Pokażemy, że T (n) = O(n log n).
Drzewo rekursji.
Drzewo rekursji jest pełnym (dzięki założeniu, że n jest potęgą 2)
Przyjmijmy, że n jest potęgą 2. Czas T (n) możemy rozwinąć w
drzewem binarnym. Każdy węzeł tego drzewa jest fragmentem
drzewo rekursji:
czasu działania algorytmu, sumując wszystkie węzły otrzymamy
cn cn
oszacowanie T (n).
Drzewo rekursji ma 2i węzłów o głębokości i, każdy z nich ma
T (n/2) T (n/2) cn/2 cn/2
wartość cn/2i, zatem ich suma wynosi cn.
T (n/4) T (n/4) T (n/4) T (n/4)
Każdy liść jest czasem sortowania podciągu jednoelementowego,
zatem jest n liści. Stąd wysokość drzewa wynosi log n.
cn
log n
cn/2 cn/2

T (n) d" cn = cn(log n + 1) = cn log n + cn = O(n log n).
i=0
cn/4 cn/4 cn/4 cn/4
. . .
c c c c c c c
Udowodnimy indukcyjnie, że T (n) d" 2c((n - 1) log n + n - 1/2)
dla dowolnego n e" 1.
Dla n = 1 mamy równość T (1) = c. Załóżmy, że n > 1 oraz
nierówność jest spełniona dla wszystkich liczb naturalnych
mniejszych niż n. Z nierówności rekurencyjnej i założenia
Ponieważ 2c((n - 1) log n + n - 1/2) = O(n log n), więc sortowanie
indukcyjnego mamy:
przez scalanie ciągu n-elementowego działa w czasie O(n log n).
Ponieważ logarytm rośnie wolniej niż jakakolwiek funkcja liniowa,
T (n) d" 2c[( n/2 -1) log n/2 +( n/2 -1) log n/2 +n-1]+cn
więc dla dostatecznie dużych n sortowanie przez scalanie jest
Korzystając z nierówności n/2 - 1 d" n/2 - 1 d" (n - 1)/2 oraz
lepsze niż sortowanie przez wstawianie, którego pesymistyczny czas
z wklęsłości logarytmu:
działania jest funkcją kwadratową zmiennej n.
log n/2 + log n/2 n/2 + n/2
d" log = log(n/2) = log n-1,
2 2
mamy:
T (n) d" 2c[(n - 1)(log n - 1) + n - 1] + cn = 2c(n - 1) log n + cn.
Pozostaje zauważyć, że cn d" 2c(n - 1/2).