Het MergeSort algoritme sorteert een lijst door de lijst op te splitsen in twee helften, deze helften recursief te sorteren, en dan de twee gesorteerde helften samen te voegen (te ‘mergen’) tot de uiteindelijke gesorteerde lijst.
Schrijf een functie mergesort die een lijst als parameter krijgt en die deze lijst sorteert via het MergeSort algoritme. De functie geeft de gesorteerde lijst terug.
>>> mergesort([45, 12, 23, 47, 72, 49, 18, 78])
[12, 18, 23, 45, 47, 49, 72, 78]