Write a program to implement merge sort

 

                         In This post we have write a c program to implement merge sort for subject of Analysis of Algorithms | Computer Engineering | Mumbai University (MU) | (Semester 4)

Program:

def merge_sort(alist, start, end):

'''Sorts the list from indexes start to end - 1 inclusive.'''

if end - start > 1:

mid = (start + end) // 2

merge_sort(alist, start, mid)

merge_sort(alist, mid, end)

merge_list(alist, start, mid, end)

def merge_list(alist, start, mid, end):

left = alist[start:mid]

right = alist[mid:end]

k = start

i = 0

j = 0

while (start + i < mid and mid + j < end):

if (left[i] <= right[j]):

alist[k] = left[i]

i = i + 1

else:

alist[k] = right[j]

j = j + 1

k = k + 1

if start + i < mid:

while k < end:

alist[k] = left[i]

i = i + 1

k = k + 1

else:

while k < end:

alist[k] = right[j]

j = j + 1

k = k + 1

alist = input('Enter the list of numbers: ').split()

alist = [int(x) for x in alist]

merge_sort(alist, 0, len(alist))

print('Sorted list: ', end='')

print(alist)

Output:

Conclusion:

Thus we perform the program to implement Merge sort.