Advertisements

Merge sort is a divide and conquer algorithm. It is based on the idea of dividing the unsorted array into several sub-array until each sub-array consists of a single element and merging those sub-array in such a way that results into a sorted array. The process step of merge sort can be summarized as follows:

**Divide:**Divide the unsorted array into several sub-array until each sub-array contains only single element.**Merge:**Merge the sub-arrays in such way that results into sorted array and merge until achieves the original array.**Merging technique:**the first element of the two sub-arrays is considered and compared. For ascending order sorting, the element with smaller value is taken from the sub-array and becomes a new element of the sorted array. This process is repeated until both sub-array are emptied and the merged array becomes sorted array.

To understand the merge sort, lets consider an unsorted array $$[4, 9, -4]$$ (right side array created after 11th process in the below diagram) and discuss each step taken to sort the array in ascending order.

At the first step, the array $$[4, 9, -4]$$ is divided into two sub-array. The first sub-array contains $$[4, 9]$$ and second sub-array contains $$[-4]$$. As the number of element in the first sub-array is greater than one, it is further divided into sub-arrays consisting of elements $$[4]$$ and $$[9]$$ respectively. As the number of elements in all sub-arrays is one, hence the further dividing of the array can not be done.

In the merging process, The sub-arrays formed in the last step are combined together using the process mentioned above to form a sorted array. First, $$[4]$$ and $$[9]$$ sub-arrays are merged together to form a sorted sub-array $$[4, 9]$$. Then $$[4, 9]$$ and $$[-4]$$ sub-arrays are merged together to form final sorted array $$[-4, 4, 9]$$

Example

# function for merge sort - splits the MyList # and call merge function to sort and merge the MyList # mergesort is a recursive function def mergesort(MyList, left, right): if left < right: mid = left + (right - left)//2 mergesort(MyList, left, mid) mergesort(MyList, mid+1, right) merge(MyList, left, mid, right) # merge function performs sort and merge operations # for mergesort function def merge(MyList, left, mid, right): # Create two temporary List to hold splitted # elements of main MyList n1 = mid - left + 1 # no of elements in LeftList n2 = right - mid # no of elements in RightList LeftList = MyList[left:mid+1] RightList = MyList[mid+1:right+1] # In below section x, y and z represents index number # of LeftList, RightList and MyList respectively x, y, z = 0, 0, left while x < n1 and y < n2: if LeftList[x] < RightList[y]: MyList[z] = LeftList[x] x+=1 else: MyList[z] = RightList[y] y+=1 z+=1 # Copying the remaining elements of LeftList while x < n1: MyList[z] = LeftList[x] x+=1 z+=1 # Copying the remaining elements of RightList while y < n2: MyList[z] = RightList[y] y+=1 z+=1 # function to print list def PrintList(MyList): for i in MyList: print(i, end=" ") print("\n") # test merge sort code MyList = [10, 1, 23, 50, 4, 9, -4] n = len(MyList) print("Original List") PrintList(MyList) mergesort(MyList, 0, n-1) print("Sorted List") PrintList(MyList)

Output

Original List 10 1 23 50 4 9 -4 Sorted List -4 1 4 9 10 23 50

In all cases (worst, average and best), merge sort always divides the array until all sub-arrays contains single element and takes linear time to merge those sub-arrays. Dividing process has time complexity $$\mathcal{O}(LogN)$$ and merging process has time complexity $$\mathcal{O}(N)$$. Therefore, in all cases, the time complexity of merge sort is $$\mathcal{O}(NLogN)$$.

Advertisements