Merge sort is a very commonly used sorting technique for arranging data in a specific order. It is based on divide and conquer technique of algorithm designing. The complexity of merge sort is O(nlogn). In this post we will create Merge Sort Python Program to show how it works. But before that we will discuss the logic and algorithm.
Merge sort is executed by dividing a list of certain elements into sub lists repeatedly till we get sub lists containing single element. At this stage the sub lists with one element are merged to create sub lists of two sorted elements. Sub lists of two sorted elements are merged to create sorted sub list of four elements. This process is continued till the original unsorted list is sorted.
If you have two stacks of notebooks sorted by the roll numbers of students and you have to make one stacked of note books sorted by roll number. The process you use will be the application of merge sort. What will you do? You will compare roll numbers of first note books of two stacks. Whichever roll number is smaller, that notebook is picked and kept separately. Again you compare roll numbers of the top note books on two stacks. Whichever roll number is smaller that note book is placed below the separately kept notebook. And this process is repeated till one of the stacks finishes. At this stage you place all the remaining notebooks of the remaining stack under the merged stack of sorted note books.
Assume that you have a list of 8 elements. The list of 8 elements is divided into two lists of 4 elements. Two lists of four elements are divided into 4 lists of two elements. 4 lists of 2 elements is divided into 8 lists of one element each. The reverse process results in four lists of two sorted elements. Then two lists of four sorted elements. In the end single list of 8 sorted elements. This is demonstrated in the image shown
Algorithm MERGING(A, BEG,MID,END) 1. [initialize variables) i=BEG j=MID+1 k=BEG 2. Repeat steps 3 and 4 while i<=MID and j< =END 3. If A[i]<A[j] then a. temp[k]=A[i] b. i=i+1 Else a. temp[k]=A[j] b. j=j+1 4. K=k+1 5. [copy remaining elements of left sub list] Repeat while( i<=MID) Temp[k]=A[i], k=k+1, i=i+1 6. [copy remaining elements of right sub list] Repeat while( j<=END) Temp[k]=A[j], k=k+1, j=j+1 7. i=BEG 8. Repeat while i<=END [copy sorted sub list to array] A[i]=temp[i] i=i+1 9. Return
ALGORITHM MERGESORT(A, N) 1. [Initialize Variables for recursive call of MERGESORT] START=1 END=N 2. IF (LOW<HIGH) [Recursive call to create sub list ends when single element sub list is created. for two sub lists MERGING function is called to sort and merge elements ] a. MIDDLE=( START + HIGH)/2 b. MERGESORT(A, START, MIDDLE) c. MERGESORT(A, MIDDLE +1, END) d. MERGING(A, START, MIDDLE, END) 3. EXIT
Merge Sort Python Program
def merging(arr, first, middle,last): i=first j=middle+1 temp= while (i<=middle) and (j<=last): if int(arr[i])<int(arr[j]): temp.append(arr[i]) i=i+1 else: temp.append(arr[j]) j=j+1 while (i<=middle): temp.append(arr[i]) i=i+1 while (j<=last): temp.append(arr[j]) j=j+1 k=first for x in temp: arr[k]=x k=k+1 def mergesort(arr,beg,end): if (beg<end): mid=int((beg+end)/2) mergesort(arr,beg,mid) mergesort(arr,mid+1,end) merging(arr,beg,mid,end) def disparr(arr,n ): i=0 print("Array elements are--->",n) while (i<n): print(arr[i]) i=i+1 arrlist= n=0 t=0 n=int(input("Number of elements you want to add--->")) while (t<n): arrlist.append(int(input("input value--->"))) t=t+1 print("Before Sorting:") disparr(arrlist,n) mergesort(arrlist,0,n-1) print("After Sorting:") disparr(arrlist,n)