Skip to main content.

Zaradenie a popis

Mergesort alebo triedenie zlučovaním je triediaci algoritmus, ktorý triedi v čase O(n log n). Je stabilný, ale netriedi na mieste. Je to algoritmus využívajúci techniku divide and conquer. Charakteristickou vlastnosťou je zlučovanie už utriedených podpostupností (merging). Používa sa napríklad pri triedení online, kde sa postupne dodávajú položky, ktoré majú byť utriedené (namiesto prístupu k celému poľu).

^ TOP

Motivácia a špecifikácia

Máme v poli uloženú postupnosť prvkov. Cieľom je usporiadať túto postupnosť vzostupne v priemernom čase O(n log n). Taktiež je požiadavka, aby bol triediaci algoritmus stabilný.
Vstup: pole A, ktoré je naplnené náhodnými hodnotami
Výstup: utriedené pole A

^ TOP

Myšlienka algoritmu

Mergesort funguje principiálne v 3 krokoch:
 1. Rozdelenie neutriedenej postupnosti na dve približne rovnaké časti.
 2. Zoradenie každej časti zvlášť (rekurzívne rozdeľovanie každej časti, až po postupnosť dĺžky 1, ktorá je samozrejme utriedená. Vtedy sa začína vynárať z rekurzie.
 3. Zlúčenie oboch častí

Mergesort zlepšuje túto rutinu dvoma myšlienkami:
 1. Na utriedenie malej postupnosti je potrebých menej krokov ako na utriedenie veľkej.
 2. Je potrebných menej krokov na vytvorenie utriedenej postupnosti z dvoch utriedených podpostupností, ako z dvoch neutriedených podpostupností. Napríklad je nutné prejsť každou podpostupnosťou len raz, pokiaľ sú už utriedené.

^ TOP

Vizualizácia

X-ová súradnica znázorňuje hodnotu prvku, Y-ová súradnica umiestnenie v poli.
Je vidieť, ako sa postupne vytvárajú utriedené podpostupnosti a tie sa zlučujú.
Autor: Nuno Nogueira, zdroj: www.wikipedia.org
Mergesort - animácia Mergesort - diagram

^ TOP

Zápis algoritmu

    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
        end if
^ TOP

Vlastnosti algoritmu

Asymptotická zložitosť pre priemerný aj najhorší prípad je O(nlog2(n)).
Velkou nevýhodou oproti algoritmom rovnakej asymptotickej rýchlosti (napríklad Heapsort) je, že Mergesort potrebuje pre svoju prácu navyše pole veľkosti N. Existuje síce aj modifikácia Mergesortu, ktorá toto pole nepotrebuje, ale jej implementácia je veľmi zložitá a pomalá. Okrem toho je Mergesort v rôznych porovnaniach pomalší ako Quicksort alebo Heapsort.
Mergesort je ale stabilný triediaci algoritmus, lepšie sa paralelizuje a má vyšší výkon na sekvenčných médiách s nižšou prístupovou dobou, lebo vyžaduje len malé množstvo pamäte s priamym prístupom. V mnohých programovacích jazykoch je Mergesort implicitným triediacim algoritmom (napríklad v Jave alebo v GNU C Library).

^ TOP

Experimentovanie

Department of Computer Science, University of British Columbia, Canada
Java applety rôznych triediacich algoritmov.
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

Computer Science Department, Princeton University, USA
Mergesort spracovaný do java appletu.
http://www.cs.princeton.edu/~ah/alg_anim/version1/MergeSort.html

^ TOP