Merge Sort

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)s
i:= 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).

Implementace v C

Související