Řazení slučováním

Řazení slučováním^[1], 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 (O(N log N)). Algoritmus je velmi dobrým příkladem programátorské metody rozděl a panuj.

Algoritmus vytvořil v roce 1945 matematik John von Neumann.

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.

Implementace v pseudokódu

function razeni_slucovanim(m)
    var list levy, pravy
    if length(m) ≤ 1
        return m
    else
        stred = length(m) / 2
        for each x in m up to stred
            add x to levy
        for each x in m after stred
            add x to pravy
        levy = razeni_slucovanim(levy)
        pravy = razeni_slucovanim(pravy)
        vysledek = sloucit(levy, pravy)
        return vysledek

Existuje několik variant pro funkci sloucit(), toto je nejjednodušší varianta:

function sloucit(levy,pravy)
    var list result
    while length(levy) > 0 and length(pravy) > 0
        if first(levy) ≤ first(pravy)
            append first(levy) to result
            levy = rest(levy)
        else
            append first(pravy) to result
            pravy = rest(pravy)
    while length(levy) > 0 
        append levy to result
        levy = rest(levy)
    while length(pravy) > 0 
        append pravy to result
        pravy = rest(pravy)
    return result

Příklad

Zde je názornější ukázka za pomocí STL algoritmu std::inplace_merge knihovny jazyka C++.

#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ř. řazení haldou) je, že řazení slučováním pro svou práci potřebuje navíc pole o velikosti N. Existuje sice i modifikace algoritmu, která toto pole nepotřebuje, ale její implementace je velmi složitá a kvůli vysoké režii i pomalá. Kromě toho je řazení slučováním ve většině případů pomalejší než rychlé řazení nebo řazení haldou.

Na druhou stranu je ř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 rychlé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 ř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 tento algoritmus. V mnoha implementacích programovacích jazyků je řazení slučováním 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 řazení slučováním.

Reference

Externí odkazy

• Obrázky, zvuky či videa k tématu řazení slučováním na Wikimedia Commons
• Jednoduchá implementace řazení slučováním v jazyku C#
• Řazení slučováním v jazyce C++