Merge sort in python

 Merge sort use divide and conquer method. In this it will divide the process or list into small subprocess or sublist then calculate and merge the subprocess/sublist into singe process/list

The entire list will be separated into sublist untill the sublist consist of one element. Merge sort is recursive algorithm after dividing into sublist it then merge the sublist item in sorted order. Two sorted list are formed into single sorted list

Algorithm:

1) if no of item>=1 exit else

2) Divide the list into two list, firstlist and secondlist until contain one element

3) Sort first and second list

4) merge the sorted list to get sorted list

Best time complexity: 0[nlogn]

Average time complexity: 0[nlogn]

Worst time complexity: 0[nlogn]

Working process:

Take list [61, 3, 43, 25, 16, 34]

           

by seeing the above diagram hope you understand the working process. Initially the list is separated into sublist until it contains one element after separated the list is merged based on the sorting order of the element.

Code  for Merge sort:

def mergeSort(list):

    

    if len(list)>1:

        mid = len(list)//2

        lefthalf = list[:mid]

        righthalf = list[mid:]

        mergeSort(lefthalf)

        mergeSort(righthalf)

        i=j=k=0       

        while i < len(lefthalf) and j < len(righthalf):

            if lefthalf[i] < righthalf[j]:

                list[k]=lefthalf[i]

                i=i+1

            else:

                list[k]=righthalf[j]

                j=j+1

            k=k+1

        while i < len(lefthalf):

            list[k]=lefthalf[i]

            i=i+1

            k=k+1

        while j < len(righthalf):

            list[k]=righthalf[j]

            j=j+1

            k=k+1

   

list = [3,54,7,24,66,34,5,8]

print("Before sorting ",list)

mergeSort(list)

print("After sorting",list)

Output :

Before sorting [3, 54, 7, 24, 66, 34, 5, 8] After sorting [3, 5, 7, 8, 24, 34, 54, 66]

Hope you understand the program and try yourself for more clear view ,feel free to comment your thoughts!!