# merge sort
l = [] # declaring list l
n = int(input("Enter number of elements in the list: ")) # taking value from user
for i in range(n):
temp = int(input("Enter element" + str(i + 1) + ': '))
l += [temp]
def merge_sort(L):
mid = int((len(L) - 1) / 2) # calculate the value of middle index of array
if len(L) > mid + 2: # this loop will run when length of array is greater than 2
a = merge_sort(L[0:mid]) # a is initialised with left side of the array taking reference as middle index
b = merge_sort(L[mid:len(L)]) # b is initialised with right side of the array taking reference as middle index
elif len(L) == 2: # this loop will when length of array is equal to 2
a = [L[0]] # a is initiliased with the first element of array
b = [L[1]] # b is initiliased with the second element of array
else:
return L
i = 0
j = 0
new = []
while (i != len(a) or j != len(
b)): # this loop will run until i is not equal to the lenth of array a or j is equal to length of array b
if i < len(a) and j < len(
b): # checking if value of i and j is lesser than length of array a and b respectively
if a[i] < b[j]: # if the element on the left side is lesser than the element on the right side
new += [a[i]] # then it will be directly added to the array new
i += 1 # i is increased by 1
else:
new += [b[
j]] # if element on the right side is lesser than the element on the left side then right side element is added to the array new
j += 1 # j increased by 1
elif i == len(a) and j != len(
b): # if i gets equal to the length of array a then all the elements of array b are directly added to the array new
new += [b[j]]
j += 1
elif j == len(b) and i != len(
a): # if j gets equal to the length of array b then all the elements of array a are directly added to the array new
new += [a[i]]
i += 1
else:
break
return new
print(merge_sort(l))