Triedenie zlučovaním

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(n\log(n))$.

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

Funkcionálny zápis tohto algoritmu vyzerá nasledovne:

mergeSort :: Ord a ⇒ [a] → [a]
mergeSort []  = []
mergeSort [x] = [x]
mergeSort s   = merge (mergeSort u) (mergeSort v)
                where (u,v) = splitAt (n `div` 2) s
                       n    = length s

merge :: Ord a ⇒ [a] → [a] → [a]
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