Urejanje z zlivanjem

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Urejanje z zlivanjem
Merge sort animation.gif
Grafični prikaz urejanja z zlivanjem
Osnovni podatki
Vrsta: algoritem za urejanje podatkov
Podatkovna struktura: tabela
Časovna zahtevnost
Zgornja meja zahtevnosti: O(n log n)
Spodnja meja zahtevnosti: O(n log n)
Pričakovana zahtevnost: O(n log n)
Prostorska zahtevnost
Prostorska zahtevnost: O(n)
Potek urejanja sedmih števil s rekurzivno implementacijo urejanja z zlivanjem

Urejanje z zlivanjem (angleško MergeSort) je stabilen algoritem za urejanje podatkov, ki ga je leta 1945 razvil John von Neumann.

Delovanje[uredi | uredi kodo]

Algoritem uporablja paradigmo 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[uredi | uredi kodo]

Časovna zahtevnost je v vseh primerih O(n \log n), prostorska zahtevnost pa je O(n), saj za podtabele potrebujemo dodaten prostor. Algoritem je možno implementirati tudi s prostorsko zahtevnostjo O(1), a pri tem izgubimo stabilnost algortima.

Psevdokoda[uredi | uredi kodo]