MERGE SORT

Algorithm

Divide the list in two half if length not = 1 or 2

sort left half 

sort right half 

merge the two 

merging:

compare the first element of each half then choose(and remove) the smaller , then check the next index of the sub list from which ele1 was chosen and repeat it until both sublists become empty

IMAGE:

CODE:

 l1=[]

n=int(input("Enter the number of elements in list: "))

for e in range(n):

    ele=int(input("Enter value for element: "))

    l1.append(ele)

print("Original list :",l1)

def merge(la,lb):

    l1=list(la)

    l2=list(lb)

    l4=[]

    i=(len(l1)+len(l2))

    while len(l4)<i:

        if len(l1)==0 or len(l2)==0:

            l4=l4+l1+l2

            break

        if l1[0]>=l2[0]:

            l4.append(l2.pop(0))

        else:

            l4.append(l1.pop(0))

    return l4

def sort(l1):

    l4=[]

    if len(l1)==2:

        if l1[0]<l1[1]:

            return l1

        else:

            return l1[::-1]

    else:

        return l1

def merge_sort(l1):

    if len(l1)==2 or len(l1)==1:

        return sort(l1)

    else:

        mid=len(l1)//2

        l2=merge_sort(l1[0:mid])

        l3=merge_sort(l1[mid:])

        return list(merge(l2,l3))

          

print("Final sorted list: ")

print(merge_sort(l1))