Merge sort

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Merge sort v akci na několika náhodných číslech

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[editovat | editovat zdroj]

Řazení pole s obsahem 7 čísel.

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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 třídění je téměř nezávislý na počátečním řazení tříděné 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 třídění nemusíme manipulovat přímo s položkami tříděné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 polí indexů můžeme mít pole setříděné "současně" podle více kritérií. 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).

Externí odkazy[editovat | editovat zdroj]