The MergeSort algorithm sorts a list by splitting it into two sublists, then recursively sorting the two sublists, and finally merging the sorted sublists into the full sorted list.

Assignment

Write a function mergesort that takes a list as parameter and that sorts this list using the MergeSort algorithm. The sorted list is returned by the function.

Example

>>> mergesort([45, 12, 23, 47, 72, 49, 18, 78])
[12, 18, 23, 45, 47, 49, 72, 78]