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.

Illustration

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)

Output