Mergesort is een efficiënt sorteeralgoritme dat gebruikmaakt van de techniek van “verdeel en heers”. Het sorteert een lijst door deze te splitsen in kleinere delen, deze delen apart te sorteren en vervolgens de gesorteerde delen samen te voegen om de uiteindelijke gesorteerde lijst te verkrijgen.

Hier is een basisstappenplan voor Mergesort:

1. Verdeel: De lijst wordt recursief in tweeën verdeeld totdat elke deellijst slechts één element bevat.
2. Sorteer: Nadat de lijst is verdeeld, worden de afzonderlijke delen gesorteerd. Dit kan worden gedaan door Mergesort opnieuw toe te passen op elk deel.
3. Voeg samen: De gesorteerde delen worden samengevoegd tot één gesorteerde lijst. Dit wordt gedaan door de elementen van beide delen te vergelijken en ze in de juiste volgorde samen te voegen.

Het samenvoegen van de gesorteerde delen gebeurt zo efficiënt mogelijk door te beginnen met de kleinste elementen van beide delen te vergelijken en deze in de resulterende lijst samen te voegen, en vervolgens verder te gaan naar de volgende elementen totdat alle elementen zijn samengevoegd.

Mergesort heeft een tijdscomplexiteit van O(n log n), wat het efficiënt maakt, zelfs voor grote lijsten. Het is echter belangrijk op te merken dat Mergesort extra geheugenruimte vereist voor het samenvoegen van de delen, wat de ruimtecomplexiteit kan verhogen.

Schrijf een functie merge_sort met een lijst van getallen als parameter die een gesorteerde lijst als returnwaarde heeft.

>>> merge_sort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]
>>> merge_sort([73, 41, 74, 72, 8, 10, 57, 84, 68, 21])
[8, 10, 21, 41, 57, 68, 72, 73, 74, 84]