Merge Sort

What is Merge Sort?

In computer science, merge sort is an efficient, general-purpose, comparison-based sorting algorithm.

Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.

It is a divide and conquers algorithm. In the divide and conquer paradigm, a problem is broken into pieces where each piece still retains all the properties of the larger problem – except its size.

Advantages of Merge Sort

1. Simple implementation.

2. Much More Efficient for small and large data sets.

3. Adaptive that is efficient for the type of data sets that are already substantially sorted.

4. Stable Sorting Algorithm

Define Merge Sorting Function

Now, let’s define a new function named merge-sorting which accepts one parameter which is list we pass as an argument to this function.

So this function is to sort an array or list using a merge sorting algorithm.

As we have discussed above, to solve the original problem, each piece is solved individually and then the pieces are merged back together.

For that, we are going to use recursive calls to a new function named merge which accepts two sorted arrays to form a single sort array.

Now in the merge-sort function, the base condition for our recursive call is that if the length of an array or list is equal to 0 or 1 then simply return the first element of the array.

Otherwise, just divide the array into two equal halves and pass both arrays to recursive calls of merge-sort.

And at last, we are going to call merge function after each recursive call to join both sorted array.

def mergeSort(x):
    if len(x) == 0 or len(x) == 1:
        return x
    else:
        middle = len(x)//2
        a = mergeSort(x[:middle])
        b = mergeSort(x[middle:])
        return merge(a,b)

Define Merge Function

Now we are breaking the array until they are divided individually. So what we want is just join the arrays that we passed in a sorted way to this function and then returned the new array as a result.

def merge(a,b):
    c = []
    while len(a) != 0 and len(b) != 0:
        if a[0] < b[0]:
            c.append(a[0])
            a.remove(a[0])
        else:
            c.append(b[0])
            b.remove(b[0])
    if len(a) == 0:
        c += b
    else:
        c += a
    return c

Complexity

The overall time complexity of Merge is O(nLogn).

The space complexity of Merge-sort is O(n).

This means that this algorithm takes a lot of space and may slow down operations for large data sets.

Define Main Condition

Now, let’s create a main condition where we need to call the above function and pass the list which needs to be sorted.

So let’s manually defined the list which we want to pass as an argument to the function.

if __name__ == '__main__':
    List = [3, 4, 2, 6, 5, 7, 1, 9]
    print('Sorted List : ',mergeSort(List))

Source Code

def merge(a,b):
    c = []
    while len(a) != 0 and len(b) != 0:
        if a[0] < b[0]:
            c.append(a[0])
            a.remove(a[0])
        else:
            c.append(b[0])
            b.remove(b[0])
    if len(a) == 0:
        c += b
    else:
        c += a
    return c

# Code for merge sort

def mergeSort(x):
    if len(x) == 0 or len(x) == 1:
        return x
    else:
        middle = len(x)//2
        a = mergeSort(x[:middle])
        b = mergeSort(x[middle:])
        return merge(a,b)

if __name__ == '__main__':
    List = [3, 4, 2, 6, 5, 7, 1, 9]
    print('Sorted List : ',mergeSort(List))

Output

Merge Sort implementation example in Python Output

JS Implementation:

Merge sort divides an array into halves, calls itself for the two halves, and then merges the two halves.

The merge algorithm consists of two functions: the mergeSort function, which takes care of partitioning the arrays, and the merge function, which merges the separate arrays.

The implementation of merge sort is the following, and is the easiest to explain using animations as example:

carbon (33).png

Screen Shot 2018-12-22 at 17.33.52.png

We invoke the mergeSort function with the array we want to have sorted. The array gets split in two parts: a left, and a right part. Then, we return the merge function with two arguments, where we call the mergeSort function for the left side of the array, and the mergeSort function for the right side of the array.

Screen Shot 2018-12-22 at 17.40.28.png

The mergeSort function gets invoked with the items on the left side of the array, which are 6 and 4. Again, this array gets split in two parts: a left, and a right part. Then, we again return the merge function, where we call the merge sort function for the left side of the array, and the mergeSort function for the right side of the array.

Screen Shot 2018-12-22 at 17.41.10.png

The mergeSort function gets invoked with the items on the left side of the array, which is only the item 6 right now. This means that array.length === 1 returns true, which returns the array.

Screen Shot 2018-12-22 at 17.41.42.png

For the first time, we invoke the mergeSort function for the right side of the array! Again, this is only one item, so array.length === 1 returns true. The array gets returned.

Screen Shot 2018-12-22 at 17.42.31.png

As both arguments returned something, the merge function actually gets called now. The merge function receives two arguments: left and right. In this case, left is 6, and right is 4. In the merge function, we declare 3 variables: a new empty array to which we will push the right values later on, the index on the left side, and the index on the right side.

leftIndex < left.length && rightIndex < right.length returns true: the length of both arrays is 1, and the index is 0. (0 < 1 && 0 < 1). The if-statement, left[leftIndex] < right[rightIndex], returns false:

left is [6], so left[0] is 6, and right is [4], so right[0] is 4! This means that the else-block gets run, and we push right[0] to the results array. The results array is now [4]. We also increment the rightIndex from 0 to 1. This means that now,

leftIndex < left.length && rightIndex < right.length returns false, because 0 < 1 && 1 < 1 is not true. The two arrays get concatenated, and returned. This means that the mergeSort(left) in the merge function we invoked first, finally returned. The exact same logic now applies to mergeSort(right).

Screen Shot 2018-12-22 at 17.44.10.png

Right now, mergeSort(left) and mergeSort(right) have returned from the very first merge call! left is [4,6] and [1, 5] is right.

Screen Shot 2018-12-22 at 17.50.35.png

Screen Shot 2018-12-22 at 17.52.12.png

The results array, displayed as the yellow box, is by default empty. The index of both the left and the right array are 0, which are displayed with the blue box. left[leftIndex] < right[rightIndex] is 4 < 1 in this case, which returns false. right[rightIndex] gets pushed to the results array, and the rightIndex get incremented by one.

Screen Shot 2018-12-22 at 17.53.23.png

As the rightIndex gets incremented by one, right[1] is now 5. 4 < 5 returns true, so left[leftIndex] gets pushed to the results array.

As the leftIndex gets incremented by one, left[1] is now 6. 6 < 5 returns false, so right[rightIndex] gets pushed to the results array.

Screen Shot 2018-12-22 at 17.55.00.png

The while-condition now returns false, which means that the results array gets returned with the leftover value concatenated. We now have our sorted array!

Screen Shot 2018-12-24 at 14.52.48.png

Best, average and worst: Each partitioning takes O(n) operations, and every partitioning splits the array O(log(n)). This results in O(n log(n)).

Worst space: We save three variables for each element in the array.