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 .

 Algoritmus 
Merge sort principiálne funguje v 3 krokoch:
 rozdelenie zoznamu na 2 časti
 zoradenie každej časti zvlášť
 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

Kategória:Triediacie algoritmy