Urejanje z zlivanjem: Razlika med redakcijama

[[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 ==

 

[[Kategorija:Algoritmi za urejanje podatkov]]