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
Iné projekty
Kategória:Triediacie algoritmy