Řazení slučováním
Merge sort je řadicí 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.
Algoritmus vytvořil v roce 1945 John von Neumann.
Algoritmus
Algoritmus pracuje následovně:
- Rozdělí neseřazenou množinu dat na dvě podmnožiny o přibližně stejné velikosti.
- Seřadí obě podmnožiny.
- Spojí seřazené podmnožiny do jedné seřazené množiny.
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)
while length(left) > 0
append left to result
left = rest(left)
while length(right) > 0
append right to result
right = rest(right)
return result
Příklad
Zde je názornější ukázka za pomocí STL algoritmu std::inplace_merge.
#include <iostream>
#include <vector>
#include <algorithm>
int main(void)
{
std::vector<unsigned> data;
for(unsigned i = 0; i < 10; i++)
data.push_back(i);
std::random_shuffle(data.begin(), data.end());
std::cout << "Initial: ";
for(unsigned i = 0; i < 9; i++)
std::cout << data.at(i) << " ";
std::cout << data.at(9) << "." << std::endl;
for(unsigned m = 1; m <= data.size(); m *= 2)
{
for(unsigned i = 0; i < data.size() - m; i += m * 2)
{
std::inplace_merge(
data.begin() + i,
data.begin() + i + m,
data.begin() + std::min<unsigned>(i + m * 2, (unsigned)data.size()));
}
}
std::cout << "Sorted: ";
for(unsigned i = 0; i < 9; i++)
std::cout << data.at(i) << " ";
std::cout << data.at(9) << "." << std::endl;
return 0;
}
Pro porovnání, zde je funkcionální varianta programu zapsaná v jazyce Haskell:
mergeSort [] = []
mergeSort [x] = [x]
mergeSort s = merge (mergeSort u) (mergeSort v)
where (u,v) = splitAt (n `div` 2) s
n = length s
merge s [] = s
merge [] t = t
merge (x:u) (y:v) = if x <= y then x : merge u (y:v)
else y : merge (x:u) v
Srovnání s ostatními řadicí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 kvůli vysoké režii i pomalá. Kromě toho je Mergesort ve většině případů pomalejší než quicksort nebo heapsort.
Na druhou stranu je Mergesort 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 quicksortu 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 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 Mergesort. V mnoha implementacích programovacích jazyků je Mergesort implicitním řadicím algoritmem (v Perlu 5.8, v Javě nebo v GNU C Library).
Pro řazení na sekvenčních mě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.
