Merge Sort is one of the most efficient sorting algorithms. The key point of the algorithm is splitting a large list to many smaller ones. By splitting a list into smaller lists, sorting them individually, and then merging them back together in order, it takes an average complexity of O(n log n).

How it works

Let's say you have a list of the following numbers [38, 27, 43, 3, 9, 82, 10]. In order to make use of the merge sort algorithm you have to split the list in two. Let's say we split it in the middle so we get the following two lists [38, 27, 43, 3] and [9, 82, 10].

Now, by using recursion we split those two lists further more to [38, 27], [43, 3],[9, 82] and [10]. We continue until all lists are split into sorted elements - simply put it a list with a single element is considered sorted.

Next, we merge in sorted order. Let's say we want to merge list [10] and [9]. We create a new list and placing the two numbers in order, [9,10]. We continue until every number is sorted.

Example

def mergesort(list):
    if len(list) > 1:
        mid = len(list) // 2
        list_a = list[:mid]
        list_b = list[mid:]

        mergesort(list_a)
        mergesort(list_b)

        index = index_a = index_b = 0

        while index_a < len(list_a) and index_b < len(list_b):
            if list_a[index_a] < list_b[index_b]:
                list[index] = list_a[index_a]
                index_a += 1
            else:
                list[index] = list_b[index_b]
                index_b += 1
            index += 1

        while index_a < len(list_a):
            list[index] = list_a[index_a]
            index_a += 1
            index += 1

        while index_b < len(list_b):
            list[index] = list_b[index_b]
            index_b += 1
            index += 1

list = [7, -1, 33, 0, -11, 89, -199]
mergesort(list)
print(list)