To write a Python Program to perform Merge sort.
Python
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
while start + i < mid:
alist[k] = left[i]
i = i + 1
k = k + 1
while mid + j < 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:
Enter the list of numbers: 1 3 2 4 5 6 7 9 8
Sorted list: [1, 2, 3, 4, 5, 6, 7, 8, 9]