Princip
- Posloupnost o jednom prvku je už seřazená.
- Mějme vstupní neseřazenou posloupnost n prvků pro n≥2
- Rozdělíme ji na dvě části poloviční délky (řekněme prvních ⌊n/2⌋ zbývajících ⌈n/2⌉ prvků).
- Rekurzivním voláním téhož algoritmu na obě poloviny jeseřadíme.
- Obě seřazené poloviny posléze sjednotíme dohromady do jedné seřazené posloupnosti a máme výsledek.
Pseudokód
Vstup: posloupnost a[1 … n]Algoritmus MergeSort
Pokud n = 1: vrať jako výsledek b1 = a1 a skonči
x1, … , x⌊n/2⌋ := MergeSort(a1, … , a⌊n/2⌋)
y1, … , y⌈n/2⌉ := MergeSort(a⌊n/2⌋ + 1, … , an)
Vrať b1, … , bn := Merge(x1, … , x⌊n/2⌋;y1, … , y⌈n/2⌉)
Algoritmus Merge(x1, … , xn; y1, … , yn)
si:= 1, j:= 1, k:= 1
Dokud i≤m a j≤n, opakujeme:
Pokud xi ≤ yj:
zk:=xi,i:= i+ 1
Jinak:
zk:=yj,j:=j+ 1
k:=k+ 1
Pokud i≤m:
zk, … , zm+n := xi, … , xm
Pokud j≤n:
zk, … , zm+n := yj, … , yn
Vrať z1, … , zm+n
Složitost
Časová složitost MergeSort je Θ(nlogn).
Důkaz pomocí Mistrovské metody
- Rozdělení posloupnosti a spojení seřazených kusů trvá čas cn. T(n) = 2T(n/2) + cn
- a=2, b= 2, nlog22 = n
- n ∈ Θ(n) ⇒ případ (2).
- Čili T(n) = Θ(nlogn).