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).

[editovat] Externí odkazy