- Deel dat wordt samengevoegd
- Vergeleken
- Teruggeschreven
- Al samengevoegd
Mergesort
Mergesort is een verdeel-en-heersalgoritme. Het halveert de lijst, sorteert elke helft op dezelfde manier en voegt de twee gesorteerde helften samen door steeds de kleinste voorste waarde te nemen. Zie hoe de helften naar een bufferrij gaan en op volgorde worden teruggeschreven, op elke snelheid of stap voor stap, en tel vergelijkingen, schrijfacties en samenvoegingen. Druk op Afspelen om het sorteren te volgen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens naartoe te springen. De tegels tellen vergelijkingen, schrijfacties terug in de lijst en samenvoegingen. Kies hoeveel staven, hoe ze beginnen, of typ je eigen getallen. Als het bord geselecteerd is, zetten de pijltjestoetsen een stap, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het eind.
Hoe het werkt
- Kies hoeveel staven en hoe ze beginnen: willekeurig, bijna gesorteerd, omgekeerd of met weinig unieke waarden. Of typ je eigen getallen.
- Druk op Afspelen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om naar elk punt in het sorteren te springen.
- Volg elke samenvoeging: de twee gesorteerde helften gaan omlaag naar de buffer, en telkens gaat de kleinste voorste waarde terug omhoog.
Hoe mergesort werkt
Eén waarde is al gesorteerd. Is de lijst langer, splits hem dan in twee helften en sorteer elke helft met mergesort. Voeg ze daarna samen: kijk naar de voorste waarde van elke helft, zet de kleinste in het resultaat en herhaal dat tot beide helften leeg zijn. Omdat beide helften gesorteerd zijn, is het resultaat dat ook.
Altijd n log n
Steeds opnieuw halveren geeft ongeveer log₂ n niveaus, en elk niveau van samenvoegingen schrijft elke waarde één keer, dus het sorteren doet ongeveer n log₂ n schrijfacties en hoogstens evenveel vergelijkingen. Anders dan bij bubblesort, selectionsort en insertionsort groeit dat niet met n², en de volgorde van de lijst maakt veel minder uit. De prijs is een buffer zo lang als de lijst. Mergesort is ook stabiel, en daarom is het de basis van het sorteren in Python en Java.
Veelgestelde vragen
Hoe werkt mergesort?
Het halveert de lijst, sorteert elke helft met mergesort en voegt de twee gesorteerde helften samen door steeds de kleinste van hun voorste waarden te nemen. Een lijst van één waarde is al gesorteerd, dus daar stopt het splitsen.
Hoeveel vergelijkingen doet mergesort?
Hoogstens ongeveer n log₂ n − n + 1, en minstens ongeveer de helft van n log₂ n, voor n waarden. Voor 40 waarden is dat hoogstens 177. Het aantal schrijfacties terug in de lijst is voor een gegeven n altijd hetzelfde: één per waarde op elk niveau van samenvoegen.
Waarom heeft mergesort extra geheugen nodig?
Twee helften ter plekke samenvoegen is lastig snel te doen, dus de gewone mergesort kopieert de helften naar een buffer en schrijft ze op volgorde terug. De buffer is zo lang als de lijst, en dat is het grootste nadeel tegenover quicksort en heapsort.
Is mergesort stabiel?
Ja. Als de twee voorste waarden gelijk zijn, gaat die uit de linkerhelft eerst, dus gelijke waarden houden hun oorspronkelijke volgorde.
Worden mijn getallen ergens naartoe gestuurd?
Nee. Het sorteren gebeurt in je browser, en je laatste instellingen blijven in de lokale opslag van deze browser.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor