В чём суть ошибки в алгоритме сортировки слиянием(MergeSort)?

Question

[Frepython]

Всем добрый день. Я полный новичок.

Совсем недавно начал учить питон как первый серьёзный язык программирования, параллельно читаю про алгоритмы.
Вопрос: ниже код алгоритма сортировки слиянием, он правильно работает только без строчки arg = list(arg)
Сама строчка, в целом, никакой смысловой нагрузки не несёт, она добавлялась с идей "вдруг там будет не список", хотя эту проблему она не решает.

Под рукой сейчас нету хорошего дебагера, а принтами я только смог понять, что значения не передаются из нижнего уровня рекурсии наверх. Без этой строчки передаются. Может кто-нибудь объяснить почему так происходит?

Спасибо.

testdata = [23,5,7,2,7,9,4]

def mergesort(arg):

    arg = list(arg)

    if len(arg)>1:

        devider = len(arg)//2 #значение для ломания списка на половины
        first_half = arg[:devider]
        second_half = arg[devider:]

        mergesort(first_half) #рекурсия левой половины

        mergesort(second_half)  #рекурсия правой половины

        i = 0
        j = 0
        k = 0
        
        while i < len(first_half) and j < len(second_half):
            
            if first_half[i] > second_half[j]:

              arg[k] = second_half[j]
              j +=1

            else:

              arg[k] = first_half[i]
              i +=1
            k +=1  

# два цикла while ниже сделаны уже с помощью интернетика. По смыслу они дозаполняют аргумент значениями
# половинок которые не попали в него в цикле выше.

        while j < len(second_half):
          arg[k] = second_half[j]
          j+=1
          k+=1

        while i < len(first_half):
          arg[k] = first_half[i]
          i+=1
          k+=1

    print('FINAL ',arg)

mergesort(testdata)

Answer 1

[Animkim]

testdata = [23,5,7,2,7,9,4]
def test(arg):
    arg.sort()

test(testdata)
print(testdata)

testdata = [23,5,7,2,7,9,4]
def test2(arg):
    arg = list(arg)
    arg.sort()

test2(testdata)
print(testdata)

Ответ лежит на поверхности, Лутц об этом пишет и приводит пример такого поведения и к чему это может привести, кажется об этом каждая книга пишет. Я конечно могу дать конкретный ответ, но думаю тут и без меня сейчас кто-нибудь вам его напишет, если самому лень перечитать главу и подумать, поэтому я только намекнул.

Comments

[Frepython]

Спасибо, этого достаточно.

В книжке про это читал, но т.к. на практике не встречал, то не закрепилось. Теперь запомнится, пойду перечитывать.

[Animkim]

Frepython, каждый на это попадался, нечего страшного.