Mergesort alebo triedenie zlučovaním je triediaci algoritmus, ktorý triedi v čase O(n log n). Je stabilný, ale netriedi na mieste. Je to algoritmus využívajúci techniku divide and conquer. Charakteristickou vlastnosťou je zlučovanie už utriedených podpostupností (merging). Používa sa napríklad pri triedení online, kde sa postupne dodávajú položky, ktoré majú byť utriedené (namiesto prístupu k celému poľu).
http://www.sprite.edi.fmph.uniba.sk/~sz ... eSort.html
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:
Kód:
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
http://sk.wikipedia.org/wiki/Mergesort
