Day 54 - Merge Sort

This is the fourth post in the Data Structures and Algorithms Series and this day I will be learning about Merge Sort. Merge Sort is one of the efficient sorting algorithms. It uses Divide and Conquer approach to sort a list of elements. It was invented by John Von Neuman in 1945.

But before we learn about merge sort we have to know what is merging.

What is Merging?

Merging is a method of combinig two sorted list to produce a single list which is also sorted.

How merging works?

First we provide merging function with two lists which are already sorted.

ls1 = [1, 3, 5, 7]
ls2 = [2, 4, 6, 8]
merge(ls1, ls2)

The merge function will take first element of both lists and compares them both to know which one is smaller and place that in the new list.

new_list = []
i = 0
j = 0
while len(ls1) != 0 and len(ls2) != 0:
    if ls1[i] < ls2[j]:
        new_list.append(ls1[i])
        ls1.pop(0)
    else:
        new_list.append(ls2[j])
        ls2.pop(0)

print(new_list) # [1, 2, 3, 4, 5, 6, 7, 8]

The Merge function will iterate over all the elements of both lists, checks which one is smaller and adds it to new sorted list while removing that element from its parent list. This way the result list is also sorted. And Now to Merge Sort.

How Merge Sort Algorithm Works?

Merge Sort follows the following steps to sort the unsorted list.

1. Divide the list into equal sublists with each containing one element as a list with one element is always sorted.
2. Repeatedly merge sublists to a new sorted sublist until all the list forms a single sorted list with all the elements of the input list.

Consider we have an unsorted list.

nums = [7, 8, 1, 3, 9, 2, 4, 5, 6, 0]

First it will divide the given list to small sublists with all having a single element in them.

nums = [[7, 1, 3, 2], [4, 5, 6, 0]]
nums = [[[7, 1], [3, 2]], [[4, 5], [6, 0]]]
nums = [
        [
            [
                [7], [1]
            ],
            [
                [3], [2]
            ]
        ],
        [
            [
                [4], [5]
            ],
            [
                [6], [0]
            ]
        ]
       ]

Then it will sort the sublists of one elements to form a sorted list of two elements. Again it will takes all those sorted sublists of two elements and sort them to form sorted lists of four elements and it will do this until the list is sorted.

1. [[[[7], [1]], [[3], [2]]], [[[4], [5]], [[6], [0]]]]
2. [[[1, 7], [2, 3]], [[4, 5], [0, 6]]]
3. [[1, 2, 3, 7], [0, 4, 5, 6]]
3. [0, 1, 2, 3, 4, 5, 6, 7]

Implementation of upcoming algorithms are going to be long so I will do the implemenentation in C along with Data Structures everytime I got some time and at some time in the future I will publish them on my GitHub.