The algorithm:

This is also a kind of divide and conquer algorithm where we divide the array into two parts and then call the same function on the two parts and finally merge the sorted halves.

For example:

Consider the following array:

[5 , 3 , 2 , 1 , 4]

This is divided into 2 arrays : [5 , 3] and [2 , 1 , 4].

Then the merge sort function is called on the two parts.

First on [5 , 3]. So, it divides into [5] and [3].

On calling again, nothing happens as none of them have a length greater than 1.

Hence, we merge these two into one array using the merge() function, which is used to merge two sorted sub arrays into one sorted array.

Hence we get [3 , 5]

We backtrack to the mergesort() call for the following array: [2 , 1 , 4].

This splits into [2] and [1 , 4] and we call the function on both of these. Since the length of the first one is not greater than one we move to the merge sort call for [1 , 4].

This splits into [1] and [4]. Since the length of both of them are not greater than one so calling mergesort() again does nothing. Next we call merge() on [1] and [4]. We thus get [1 , 4].

We then backtrack to the mergesort() call of [2 , 1 , 4] and call merge on [2] and [1 , 4]. Hence, we are left with [1 , 2 , 4]

Finally, we return to the first call of mergesort() on [5 , 3 , 2 , 1 , 4] and we call merge() on [3 , 5] and [1 , 2 , 4]

Finally, we are left with the sorted array of [1 , 2 , 3 , 4 , 5].

This is how the algorithm works.

The program:

def merge(a , l , r):
   i = 0
   j = 0
   f = 0
 
   while i < len(l) and j < len(r):
       if l[i] < r[j]:
           a[f] = l[i]
           i+=1
           f+=1
       else:
           a[f] = r[j]
           j+=1
           f+=1
    
   while i < len(l):
       a[f] = l[i]
       i+=1
       f+=1
    
   while j < len(r):
       a[f] = r[j]
       j+=1
       f+=1
    
def mergesort(a):
   if len(a) > 1:
       m = len(a)//2
       l = a[:m]
       r = a[m:]
       mergesort(l)
       mergesort(r)
       merge(a,l,r)
       return a
 
print("Enter the array you want to sort:")
a = [int(i) for i in input().split()]
print("the sorted array is:")
print(mergesort(a))

The output of the above program is as follows:

Time Complexity:  O(nlogn)

The github link of the above program is:

https://github.com/HSNA243/PythonPrograms/blob/master/MergeSort.py

Picture from:

Designed by Freepik
Visits: 42

Leave a Reply

Your email address will not be published. Required fields are marked *