Triedenie zlučovaním

Z Wikipédie

Triedenie zlučovaním (merge sort) je triediaci algoritmus, netriedi na mieste.

Tento algoritmus triedenia mal veľký význam v minulosti pri triedení údajov na magnetických páskach (médium so sekvenčným prístupom), keďže vyžaduje len malé množstvo pamäte s priamym prístupom.

Asymptotická zložitosť pre priemerný aj najhorší prípad je O(nlog₂(n)).

[úprava] Algoritmus

Merge sort principiálne funguje v 3 krokoch:

1. rozdelenie zoznamu na 2 časti
2. zoradenie každej časti zvlášť
3. zlúčenie oboch častí

Jeho jednoduchý zápis by vyzeral asi takto:

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