Mergesort
Splitst de lijst in twee helften, sorteert elke helft en voegt de twee gesorteerde helften daarna samen tot één gesorteerde lijst.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(n)
- ja
- nee
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
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.