Mergesort

Splitst de lijst in twee helften, sorteert elke helft en voegt de twee gesorteerde helften daarna samen tot één gesorteerde lijst.

beste geval Ω(n log n)
gemiddeld Θ(n log n)
slechtste geval O(n log n)
geheugen O(n)
stabiel
heeft extra geheugen nodig

Wat betekent dit?

Beste geval: hoe de tijd groeit met de lijstgrootte n als de invoer voor dit algoritme het makkelijkst is.
Gemiddeld: de gewone groei van de tijd met n. Bij n² duren twee keer zoveel waarden ongeveer vier keer zo lang. n log n groeit veel trager.
Slechtste geval: de groei bij de moeilijkste invoer. Handig als de snelheid nooit mag inzakken.
Geheugen: hoeveel extra geheugen nodig is naast de lijst. 1 betekent een paar variabelen, n een kopie van de lijst.
Stabiel: twee gelijke waarden houden hun oorspronkelijke volgorde. Belangrijk als je records op één veld sorteert.
Zonder extra geheugen: sorteert in de lijst zelf, zonder tweede lijst.

wordt vergeleken
wordt verplaatst
op definitieve plek

0 / 263 stappen

Vergelijkingen Schrijfacties

Druk op afspelen: de lijnen tonen hoe de kosten oplopen

Snelheid 8 stappen / s

Spatie: afspelen of pauzeren. Pijltjes links/rechts: stap. Home en End: springen.

Probeer dit: Kies een lijst met weinig unieke waarden. Van twee gelijke waarden gaat die uit de linkerhelft eerst, zo blijft hun volgorde behouden.

Hoe het werkt

Blijf de lijst splitsen tot elk stukje één waarde heeft. Zo'n stukje is al gesorteerd. Voeg de stukjes daarna per paar weer samen: vergelijk de eerste waarden van beide stukjes en neem de kleinste, steeds opnieuw. De opgetilde rij in de animatie is de extra ruimte die het samenvoegen nodig heeft.

Wanneer het een goede keuze is

Als je snelheid nodig hebt die ook in het slechtste geval goed blijft, en gelijke waarden hun volgorde moeten houden. Python en Java gebruiken allebei een versie van mergesort. Het nadeel is het extra geheugen.