Merge Sort is a sorting algorithm which is based on divide and conquer approach. The list is divided into two halves until each sub list has a single element, and the sub lists are merged in a sorted manner that the sorted list is obtained. It is a very efficient algorithm for sorting. The technique simply involves: Divide the list into two sub slists, Make recursion call for the sub lists, and then Merge the sub lists.
if length(list)>1 find point of divide,mid=length(list)//2 left sublist L,index 0 to mid right sublist R, index mid+1 to length(list)-1 recursion,calling function itself for L recursion,calling function itself for R i=j=k=0 while i<length(L) and j<length(R) if L[i] < R[j],then list[k]=L[i] and i=i+1 else, list[k]=R[j] and j=j+1 k=k+1 while i<length(L) list[k]=L[i] update i=i+1 and k=k+1 while i<length(R) list[k]=R[j] update j=j+1 and k=k+1
Time Complexity: Worst Case: O(nlogn) Average Case: O(nlogn) Best Case: O(nlogn) Space Complexity: O(n)
Program for Merge Sort:
def mergeSort(data): if len(data) > 1: mid = len(data)//2 #point where the list is divided into two sublists L = data[:mid] R = data[mid:] mergeSort(L) #sorting first half mergeSort(R) #sorting second half i = j = k = 0 while i < len(L) and j < len(R): if L[i] < R[j]: data[k] = L[i] i += 1 else: data[k] = R[j] j += 1 k += 1 while i < len(L): data[k] = L[i] i += 1 k += 1 while j < len(R): data[k] = R[j] j += 1 k += 1 inp=input("Enter the data: ").split() data= for i in inp: data.append(int(i)) mergeSort(data) print("Sorted List is: ") print(data)