Merge Sort Algorithm

Write a Python Program to perform Merge sort. 

Program Algorithm:

1. Create a function named mergesort

2. Find the mid of the list

3. Assign lefthalf = alist[:mid] and righthalf = alist[mid:]

4. Initialise i=j=k=0

5. while i < len(lefthalf) and j < len(righthalf), perform the following

if lefthalf[i] < righthalf[j]:

alist[k]=lefthalf[i]

Increment i

 else

 alist[k]=righthalf[j]

Increment j

Increment k

6. while i < len(lefthalf),perform the following

 alist[k]=lefthalf[i]

Increment i

Increment k

7. while j < len(righthalf), perform the following

alist[k]=righthalf[j]

Increment j

Increment k

8. Print the sorted list  

Program Code:

def mergeSort(alist):

 # print("Splitting ",alist)

 if len(alist)>1:

 mid = len(alist)//2

 lefthalf = alist[:mid]

 righthalf = alist[mid:]

 mergeSort(lefthalf)

 mergeSort(righthalf)

 i=j=k=0

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

 if lefthalf[i] < righthalf[j]:

 alist[k]=lefthalf[i]

 i=i+1

 else:

 alist[k]=righthalf[j]

 j=j+1

 k=k+1

 while i < len(lefthalf):

 alist[k]=lefthalf[i]

 i=i+1

 k=k+1

 while j < len(righthalf):

 alist[k]=righthalf[j]

 j=j+1

 k=k+1

 #print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]

mergeSort(alist)

print(alist)  

Program Output:

 [17, 20, 26, 31, 44, 54, 55, 77, 93]