Mergesort

Mergesort maakt van één moeilijk probleem veel makkelijke: twee gesorteerde lijsten zijn eenvoudig tot één te combineren. Halveer de lijst tot elk stuk één waarde is, en voeg de stukken daarna weer samen. Het is het klassieke verdeel-en-heersalgoritme, en de tijd is n log n, wat de invoer ook is.

Twee gesorteerde helften van een lijst in een bufferrij, en de kleinste voorste waarde die terug omhoog de lijst in gaat
Twee gesorteerde helften van een lijst in een bufferrij, en de kleinste voorste waarde die terug omhoog de lijst in gaat

Het idee

Samenvoegen is het makkelijke deel. Neem twee lijsten die elk gesorteerd zijn, vergelijk hun eerste waarden en neem de kleinste. Vergelijk de nieuwe eerste waarden en neem weer de kleinste. Raakt een lijst op, zet dan de rest van de andere erachter. Elke stap neemt één waarde, dus twee lijsten met samen lengte m samenvoegen kost hoogstens m − 1 vergelijkingen. Mergesort gebruikt dat om te sorteren: halveer de lijst, sorteer elke helft met mergesort en voeg de twee helften samen.

Een voorbeeld

Neem 5, 1, 4, 2, 8. Splits dat in 5, 1 en 4, 2, 8. De eerste helft splitst in 5 en 1, die samen 1, 5 worden. De tweede helft splitst in 4 en 2, 8; de 2, 8 ontstaat uit 2 en 8 en wordt daarna met 4 samengevoegd tot 2, 4, 8. Ten slotte worden 1, 5 en 2, 4, 8 samengevoegd: 1, dan 2, dan 4, dan 5, en 8 blijft over. Dat zijn 8 vergelijkingen, 12 schrijfacties en 4 samenvoegingen.

Waarom n log n

Elke splitsing halveert de stukken, dus na ongeveer log₂ n niveaus is elk stuk één waarde. Op de weg terug verwerkt elk niveau van samenvoegingen elke waarde één keer: n schrijfacties en minder dan n vergelijkingen per niveau. In totaal is dat ongeveer n log₂ n. Voor 40 waarden doet het sorteren 216 schrijfacties en hoogstens 177 vergelijkingen; bubblesort kan voor dezelfde lijst 780 vergelijkingen nodig hebben. De volgorde van de invoer maakt veel minder uit dan bij die methoden: voor 40 waarden kost een gesorteerde lijst 100 vergelijkingen, een omgekeerde 116 en een willekeurige ongeveer 160.

De buffer, en stabiliteit

Om twee helften samen te voegen die naast elkaar in de lijst staan, kopieert de gewone methode ze naar een buffer en schrijft ze op volgorde terug. De app toont die buffer als de tweede rij staven. Er is evenveel extra geheugen nodig als de lijst inneemt, en dat is de grootste kostenpost van mergesort. In ruil daarvoor is het sorteren stabiel: als de twee voorste waarden gelijk zijn, gaat die uit de linkerhelft eerst, dus gelijke waarden houden hun volgorde. Stabiliteit is belangrijk als je records op het ene veld na het andere sorteert.

Geschiedenis en gebruik

John von Neumann beschreef mergesort in 1945, waarmee het een van de eerste algoritmen is die voor een computer met opgeslagen programma zijn geschreven. Omdat het gegevens in lange reeksen leest en schrijft, was het de standaardmethode om gegevens op tape te sorteren, en het wordt nog steeds gebruikt voor bestanden die te groot zijn voor het geheugen. Timsort, dat Python gebruikt en Java voor objecten, is een mergesort die eerst reeksen zoekt die al gesorteerd zijn en insertionsort gebruikt voor korte stukken.

John von Neumann, op zijn badgefoto van Los Alamos. In 1945 beschreef hij mergesort, een van de eerste algoritmen voor een computer met opgeslagen programma.
John von Neumann, op zijn badgefoto van Los Alamos. In 1945 beschreef hij mergesort, een van de eerste algoritmen voor een computer met opgeslagen programma.

Probeer het zelf

Open de app en druk op Stap. Het gearceerde deel van de lijst wordt gesplitst of samengevoegd, en de stippellijn markeert het midden. Als een samenvoeging begint, zakken beide helften naar de bufferrij; de twee voorste waarden worden vergeleken, en de kleinste gaat terug omhoog. Let op de tellers: de schrijfacties zijn gelijk voor elke lijst van dezelfde lengte, en de vergelijkingen zijn het laagst voor een gesorteerde of omgekeerde lijst en het hoogst voor een willekeurige, maar nooit meer dan ongeveer n log₂ n.

Veelgestelde vragen

Wat is de tijdcomplexiteit van mergesort?

O(n log n) in het beste, gemiddelde en slechtste geval. De gewone versie heeft O(n) extra geheugen nodig voor de buffer.

Wat is het verschil tussen mergesort en quicksort?

Beide verdelen de lijst en sorteren de delen. Mergesort splitst in het midden zonder naar de waarden te kijken en doet het werk bij het samenvoegen; quicksort doet het werk bij het splitsen, door waarden rond een spil te verplaatsen, en hoeft niet samen te voegen. Quicksort sorteert ter plekke en is in de praktijk vaak sneller, maar kan bij slechte invoer vertragen tot n² en is niet stabiel. Mergesort is altijd n log n en stabiel.

Wat is bottom-up mergesort?

Een versie zonder recursie: voeg eerst naburige losse waarden samen tot paren, dan paren tot viertallen, enzovoort, zodat de lengte elke ronde verdubbelt. Het doet hetzelfde werk als de top-down versie die hier wordt getoond.

Is mergesort stabiel?

Ja, zolang bij gelijke waarden die uit de linkerhelft eerst gaat, zoals in deze app.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Probeer mergesort