Mergesort

Mergesort is een enorme verbetering over het Bubblesort algoritme. Het is ook een sorteeralgoritme en dient dus ook om een lijst van getallen te sorteren, maar het doet dit veel efficiënter dan Bubblesort. Onderstaande animatie toont hoe MergeSort werkt;

Het achterliggende idee van MergeSort is een heel belangrijke fundamentele programmeertechniek genaamd verdeel-en-heers. Bij verdeel-en-heers verdelen we het opgegeven probleem in kleinere stukjes die makkelijker op te lossen zijn en die we makkelijk kunnen samenvoegen tot een oplossing voor het originele probleem. Specifiek redeneert Mergesort als volgt:

  1. Een lijst die exact één getal bevat, is al gesorteerd.
  2. Twee gesorteerde lijsten kunnen we snel samenvoegen tot één grote gesorteerde lijst.

Het eerste punt is duidelijk. Het tweede punt kunnen we illustreren aan de hand van een voorbeeld. Stel dat je de gesorteerde lijsten [2, 4, 6, 8] en [1, 3, 5, 7] moet samenvoegen tot één gesorteerde lijst. Je kan dan beurtelings het kleinste element van de twee lijsten eruithalen en zo een volledig gesorteerde lijst opbouwen. Specifiek ga je als volgt te werk in dit voorbeeld:

  1. We kijken naar 2 en 1. Het minimum is 1.
  2. We kijken naar 2 en 3. Het minimum is 2.
  3. We kijken naar 4 en 3. Het minimum is 3.
  4. We kijken naar 4 en 5. Het minimum is 4.
  5. We kijken naar 6 en 5. Het minimum is 5.
  6. We kijken naar 6 en 7. Het minimum is 6.
  7. We kijken naar 8 en 7. Het minimum is 7.
  8. Er blijft enkel nog maar 8 over.

Zo krijgen we de volledig gesorteerde lijst [1, 2, 3, 4, 5, 6, 7, 8].

De werking van Mergesort bestaat erin de originele lijst te blijven opsplitsen in twee ongeveer even grote delen totdat het sorteren triviaal wordt, en die gesorteerde delen vervolgens efficiënt samen te voegen tot één geheel. Stel dat de invoer bijvoorbeeld [5, 4, 3, 2, 1] is. In eerste instantie splitst Mergesort deze lijst dan in twee:

[5, 4, 3]
[2, 1]

Deze twee delen worden nog verder opgesplitst:

[5, 4]
[3]

[2]
[1]

En nog verder:

[5]
[4]

[3]

[2]
[1]

Het samenvoegen van de lijsten [2] en [1] volgens de procedure die hierboven beschreven werd, is eenvoudig:

  1. We kijken naar 2 en 1. Het minimum is 1.
  2. Er blijft enkel 2 over.

Dit gebeurt ook voor [5] en [4]. We krijgen zo

[4, 5]
[3]

[1, 2]

Nu voegen we [4, 5] en [3] samen:

[3, 4, 5]
[1, 2]

Tenslotte voegen we deze laatste twee lijsten nog samen:

[1, 2, 3, 4, 5]

De lijst is gesorteerd!

Opgave

Implementeer het Mergesort-algoritme om een lijst van getallen te sorteren. De meest praktische manier om Mergesort te implementeren, is via recursie, de programmeertechniek waarbij een functie zichzelf opnieuw oproept. Dit moet natuurlijk op zo'n manier gebeuren dat we niet oneindig blijven doorgaan! Voor Mergesort ziet de implementatie er ongeveer zo uit:

def mergesort(getallen):
    # controleer de lengte
    if len(getallen) == 1:
        # de lijst is al gesorteerd
        return getallen

    # splits de lijst met getallen in twee ongeveer gelijke delen
    eerste_helft = ...
    tweede_helft = ...

    # roep Mergesort recursief aan
    eerste_helft = mergesort(eerste_helft)
    tweede_helft = mergesort(tweede_helft)

    # voeg de lijsten samen
    gesorteerd = []
    ...

    return gesorteerd

Dit werkt omdat Mergesort zichzelf enkel oproept op lijsten die korter zijn dan de lijst waarmee het algoritme begonnen is. Uiteindelijk gaan deze lijsten maar één element meer bevatten en belanden we in de return op regel 5, waarmee de uitvoering termineert.

Voorbeeld

Invoer:

14
70
35
27
37
93
7
73
68
64

Uitvoer:

7
14
27
35
37
64
68
70
73
93

Indienen

Evaluatie


Uitvoerconsole