Urejanje z zlivanjem: razlika med redakcijama

m
dp
m (restub)
m (dp)
[[Slika:Merge_sort_animation.gif|thumb|300px|Grafični prikaz urejanja z zlivanjem]]
[[Slika:Merge_sort_algorithm_diagram.svg.png|thumb|300px|Potek urejanja sedmih števil s rekurzivno implementacijo urejanja z zlivanjem]]
 
'''Urejanje z zlivanjem''' ({{jezik-en|MergeSort}}) je stabilen [[Algoritmi za urejanje podatkov|algoritem za urejanje podatkov]], ki ga je leta 1945 razvil [[John von Neumann]].
 
== Delovanje ==
 
Algoritem uporablja paradigmo [[Deli in vladaj (računalništvo)|deli in vladaj]]. Začne s podtabelami velikosti 1, ki so same po sebi seveda urejene. Nato začne z zlivanjem(in sprotnim urejanjem) parov podtabel v večjo podtabelo in te tabele nato zopet zliva v večje, dokler ne zlije vseh elementov tabele v eno urejeno tabelo.
 
== Zahtevnost ==
 
[[Časovna zahtevnost]] je v vseh primerih <math>O(n \log n)</math>, [[prostorska zahtevnost]] pa je <math>O(n)</math>, saj za podtabele potrebujemo dodaten prostor. Algoritem je možno implementirati tudi s prostorsko zahtevnostjo <math>O(1)</math>, a pri tem izgubimo stabilnost algortima.
 
== Psevdokoda ==
 
{{comp-stub}}
{{računalniška škrbina}}
 
[[Kategorija:Algoritmi za urejanje podatkov]]