Merge sort
Z Wikipedie, otevřené encyklopedie
Merge sort je řadící algoritmus, jehož průměrná i nejhorší možná časová složitost je (O(N log N)). Algoritmus je velmi dobrým příkladem programátorské metody rozděl a panuj.
Obsah |
[editovat] Algoritmus
Algoritmus pracuje následovně:
1) Rozdělí neseřazenou množinu dat na dvě podmnožiny o přibližně stejné velikosti
2) Seřadí obě podmnožiny
3) Spojí seřazené podmnožiny do jedné seřazené množiny
Algoritmus vytvořil v roce 1945 John von Neumann.
[editovat] Implementace v pseudokódu
function mergesort(m) var list left, right if length(m) ≤ 1 return m else middle = length(m) / 2 for each x in m up to middle add x to left for each x in m after middle add x to right left = mergesort(left) right = mergesort(right) result = merge(left, right) return result
Existuje několik variant pro funkci merge(), toto je nejjednodušší varianta:
function merge(left,right) var list result while length(left) > 0 and length(right) > 0 if first(left) ≤ first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) if length(left) > 0 append left to result if length(right) > 0 append right to result return result
[editovat] Srovnání s ostatními řadícími algoritmy
Velkou nevýhodou oproti algoritmům stejné rychlostní třídy (např. Heapsort) je, že Mergesort pro svou práci potřebuje navíc pole o velikosti N. Existuje sice i modifikace Mergesortu, která toto pole nepotřebuje, ale její implementace je velmi složitá a díky vysokému overheadu i pomalá. Kromě toho se Mergesort také ukazuje být pomalejší než Quicksort nebo Heapsort. Na druhou stranu je Mergesort stabilní řadící algoritmus, lépe se paralelizuje a má vyšší výkon na sekvenčních médiích s nižší přístupovou dobou. V mnoha implementacích programovacích jazyků je Mergesort implicitním řadícím algoritmem (v Perlu 5.8, v Javě nebo v GNU C Library).