|
[[Soubor:Merge sort animation2.gif|frame|MergeŘazení sortslučováním v akci na několika náhodných číslech]]
'''MergeŘazení slučování''', známé také pod anglickým názvem '''merge sort''', je [[řadicí algoritmus]], jehož průměrná i nejhorší možná časová složitost je ([[asymptotická složitost|''O'']](''N'' log ''N'')). Algoritmus je velmi dobrým příkladem programátorské metody [[rozděl a panuj (algoritmus)|rozděl a panuj]].
Algoritmus vytvořil v roce [[1945]] matematik [[John von Neumann]].
== Algoritmus ==
== Implementace v pseudokódu ==
'''function''' mergesortrazeni_slucovanim(m)
'''var''' ''list'' leftlevy, rightpravy
'''if''' length(m) ≤ 1
'''return''' m
'''else'''
middlestred = length(m) / 2
'''for each''' x '''in''' m '''up to''' middlestred
add x to leftlevy
'''for each''' x '''in''' m '''after''' middlestred
add x to rightpravy
leftlevy = mergesortrazeni_slucovanim(leftlevy)
rightpravy = mergesortrazeni_slucovanim(rightpravy)
resultvysledek = mergesloucit(leftlevy, rightpravy)
'''return''' resultvysledek
Existuje několik variant pro funkci mergesloucit(), toto je nejjednodušší varianta:
'''function''' mergesloucit(leftlevy,rightpravy)
'''var''' ''list'' result
'''while''' length(leftlevy) > 0 '''and''' length(rightpravy) > 0
'''if''' first(leftlevy) ≤ first(rightpravy)
append first(leftlevy) to result
leftlevy = rest(leftlevy)
'''else'''
append first(rightpravy) to result
rightpravy = rest(rightpravy)
'''while''' length(leftlevy) > 0
append leftlevy to result
leftlevy = rest(leftlevy)
'''while''' length(rightpravy) > 0
append rightpravy to result
rightpravy = rest(rightpravy)
'''return''' result
== Příklad ==
Zde je názornější ukázka za pomocí [[Standard Template Library|STL]] algoritmu ''std::inplace_merge'' knihovny jazyka C++.
<source lang="C++">
#include <iostream>
== Srovnání s ostatními řadicími algoritmy ==
Velkou nevýhodou oproti algoritmům stejné rychlostní třídy (např. [[heapsortřazení haldou]]) je, že Mergesortřazení slučováním pro svou práci potřebuje navíc pole o velikosti N. Existuje sice i modifikace Mergesortualgoritmu, která toto pole nepotřebuje, ale její implementace je velmi složitá a kvůli vysoké režii i pomalá. Kromě toho je Mergesortřazení slučováním ve většině případů pomalejší než [[quicksortrychlé řazení]] nebo [[heapsort]]řazení haldou.
Na druhou stranu je Mergesortřazení slučováním [[stabilní řadicí algoritmus]], lépe se paralelizuje a má vyšší výkon na sekvenčních médiích s nižší přístupovou dobou. Velkou výhodou proti [[quicksort]]urychlému řazení je, že čas potřebný pro řazení je téměř nezávislý na počátečním seřazení posloupnosti. Vyšší spotřeba paměti není tak velkým problémem jak se může na první pohled zdát, protože při řazení nemusíme manipulovat přímo s položkami řazeného pole, ale pouze s polem indexů, které v paměti většinou zabírá mnohem méně místa. Při použití více indexů můžeme každý index seřadit podle jiného kritéria, což ale není specifické pro Mergesortřazení slučováním a běžně se používá v databázových indexech. Něco jiného je, že konkrétní řazení může být podle víc kritérií, obvykle zkombinovaných lexikograficky, což ale také není specifické pro Mergesorttento algoritmus. V mnoha implementacích programovacích jazyků je Mergesortřazení slučováním implicitním řadicím algoritmem (v [[Perl]]u 5.8, v [[Java (programovací jazyk)|Javě]] nebo v [[GNU C Library]]).
Pro řazení na sekvenčních mědiíchmédiích se používají jiné algoritmy založené na slučování seřazených (pod)posloupností, které se ale nepovažují za Mergesortřazení slučováním.
== Externí odkazy ==
* [http://www.martinvseticka.eu/index.php?sekce=browse&page=54 Jednoduchá implementace Mergeřazení sortuslučováním v jazyku C#]
* [https://web.archive.org/web/20060719144833/http://24bytes.com/Merge-Sort.html MergeŘazení sortslučováním v jazyce C++]
{{Pahýl}}
| 