A Simple Implementation of Merge Sort in Python

Understand Merge Sort in 6 Minutes

Understand Merge Sort in 6 Minutes

Merge sort is one of the algorithms you need to master. Why?

Because it is in the class of efficient algorithms and is easy to understand.

But what does efficient mean?

Let’s get back to that. First how does Merge Sort work?

Merge Sort explained

It takes the list and breaks it down into two sub lists. Then it takes these sublists and break them down into two. This process continues until there is only 1 element in each sublist.

And a list containing only 1 element, is a sorted list.

Merge Sort explained

It then takes two sublists and merge them together. Notice, that each of these sublists (in the first place, the sublists only contain 1 element each) are sorted.

Then it is effective to merge them together sorted. The algorithm looks at the first element of each sorted sublist and takes the smaller element first.

Merge Sort explained

This process continues all the way down.

Then the next row is taken of sublists. Again, the sample algorithm is used to merge them together. Take the smaller element of the two and add them to the new list. This continues.

Merge Sort explained

This process continues until we end up with one list.

Merge Sort explained

Which by magic (or the logic behind the algorithm) is sorted.

Time complexity

Well, we talked about it is one of the efficient sorting algorithm. That means it runs in O(N log(N)) time.

That means, if you have a list of N unsorted elements, it will take N log(N) operations.

Is that true for Merge Sort?

How many layers do you have in the algorithm?

Well, for each layer you half the size of each sublist. You can do that log(N) times.

For each layer, you do N comparisons. That results in N log(N) operations, hence, the O(N log(N)) time complexity.

The implementation of Merge Sort in Python

def merge_sort(my_list):
    if len(my_list) <= 1:
        return my_list

    mid = len(my_list)//2
    left_list = my_list[:mid]
    right_list = my_list[mid:]

    merge_sort(left_list)
    merge_sort(right_list)

    index_left = 0
    index_right = 0
    index_main = 0

    while index_left < len(left_list) and index_right < len(right_list):
        if right_list[index_right] < left_list[index_left]:
            my_list[index_main] = right_list[index_right]
            index_right += 1
            index_main += 1
        else:
            my_list[index_main] = left_list[index_left]
            index_left += 1
            index_main += 1

    while index_left < len(left_list):
        my_list[index_main] = left_list[index_left]
        index_left += 1
        index_main += 1

    while index_right < len(right_list):
        my_list[index_main] = right_list[index_right]
        index_right += 1
        index_main += 1


def main():
    my_list = [19, 56, 8, -6, -3, 27, -9, -29]
    print(my_list)
    merge_sort(my_list)
    print(my_list)


if __name__ == "__main__":
    main()

That is awesome.

Want to learn more about sorting. Check out the Insertion Sort, which is also one of the sorting algorithms you need to master. It is not as efficient, but it has one advantage you need to understand.

Leave a Reply