Блог

Моя реализация:

 def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    left = arr[:len(arr)//2]
    right = arr[len(arr)//2:]

    merge_sort(left)
    merge_sort(right)

    return merge(left, right)

def merge(left, right):
    leftI = rightI = 0
    merged = []
    
    while (leftI < len(left) and rightI < len(right)):
        if left[leftI] < right[rightI]:
            merged.append(left[leftI])
            leftI  = 1
        else:
            merged.append(right[rightI])
            rightI  = 1
    
    merged.extend(left[leftI:])
    merged.extend(right[rightI:])
    
    return merged

if __name__ == '__main__':
    arr = [1,2,5,5,9,22,6,3,6,8,1,43,5]
    print(merge_sort(arr))
 

По какой-то причине я получаю:

[1, 2, 5, 5, 6, 3, 6, 8, 1, 9, 22, 43, 5]

Рабочая реализация (получена от друга):

 def merge_sort(list):
    list_length = len(list)

    if list_length == 1:
        return list

    mid_point = list_length // 2

    left_partition = merge_sort(list[:mid_point])
    right_partition = merge_sort(list[mid_point:])

    return merge(left_partition, right_partition)


def merge(left, right):
    output = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            output.append(left[i])
            i  = 1
        else:
            output.append(right[j])
            j  = 1
            
    output.extend(left[i:])
    output.extend(right[j:])

    return output

if __name__ == '__main__':
    arr = [1,2,5,5,9,22,6,3,6,8,1,43,5]
    print(merge_sort(arr))
 

Этот код соответствует:

[1, 1, 2, 3, 5, 5, 5, 6, 6, 8, 9, 22, 43]

Я просто не могу понять, что не так. Было бы большим подспорьем, если бы кто-нибудь мог уделить мне несколько минут, чтобы помочь 🙂

В вашей merge_sort функции вы не меняете значения left и right в зависимости от того, что merge_sort возвращает. У тебя есть :

 merge_sort(left)
merge_sort(right)
 

Где это должно быть :

 left = merge_sort(left)
right = merge_sort(right)