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(nlog2(n)).
[úprava] 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

