Мой код для сортировки слиянием возвращает мне тот же входной массив

Question

Ниже приведен код для Mergesort с pivot, установленным в качестве первого элемента. Этот код генерирует мне выходной массив, который совпадает с входным.

Код Python3:

def mergesort(array):
    length=len(array)
    if(length<=1):
        return (array)
    else:
        mid=length//2
        left=[]
        right=[]
        # print(mid)
        left=mergesort(array[0:mid])
        right=mergesort(array[mid:])
        # print(left, right)
        arr=merge(left,right)
        return (array)

def merge(left,right):

    # print(left, right)
    i=j=0
    # l=len(left+right)
    l1=len(left)
    l2=len(right)
    l=l1+l2
    arr=list()
    for k in range(l):
        if i == l1:
            arr.append(right[j])
            j+=1
        elif j == l2:
            arr.append(left[i])
            i+=1
        elif(left[i] > right[j]):
            arr.append(right[j])
            j=j+1
        elif (left[i] < right[j]):
            arr.append(left[i])
            i=i+1
        # print(array)
    return (arr)

array=list(map(int,input().split()))
# print(array)
print(mergesort(array))

Это скриншот моей программы:

Answer 1

В коде есть две ошибки:

Во-первых, у вас есть опечатка в строке 14:

def mergesort(array):
    #....
    arr=merge(left,right)
    return (arr) # Not return (array)

Во-вторых, ваш код не работает со специальными входами, поскольку вы не реализовали случай <= или >= при выполнении операции слияния. Так, например, ваш код не может сортировать 2 5 3 5. Чтобы это исправить:

def merge(left,right):
    # ...
    elif(left[i] > right[j]):
        arr.append(right[j])
        j=j+1
    elif (left[i] <= right[j]): # instead of <
        arr.append(left[i])
        i=i+1