Рекурсия алгоритма сортировки слиянием

Question

Я начал изучать python несколько дней назад и пытался решить алгоритмы сортировки. Я недавно начал с алгоритма сортировки слиянием. Типичная программа сортировки слиянием в python (насколько я знаю) включает функцию слияния и функцию слияния. Следующие строки являются общими для всех программ, которые я видел:

left = mergesort(left)
right = mergesort(right)
merge(left, right)

Например, в этом коде:

def divide_arr(a):    #same as mergesort function
    l = len(a)
    if l <= 1: return a
    left = a[0:int(l/2)]
    right = a[int(l/2):l]
    left = divide_arr(left)
    right = divide_arr(right)
    return merge(left, right, a)

def merge(left, right, arr):
    pl, pr, pa = 0, 0, 0
    while pl <len(left) and pr < len(right):
        if left[pl] <= right[pr]:
            arr[pa] = left[pl]
            pa += 1
            pl += 1
        elif left[pl] > right[pr]:
            arr[pa] = right[pr]
            pa += 1
            pr += 1
    while pl < len(left):
        arr[pa] = left[pl]
        pa += 1
        pl += 1
    while pr < len(right):
        arr[pa] = right[pr]
        pa += 1
        pr += 1
    return arr

Я действительно не уверен, как компилятор интерпретирует эти строки.

Давайте возьмем массив [4,3,2,1]. Поэтому, когда я вызываю mergesort, первый левый массив становится = [4,3], а правый = [2,1]

Теперь, когда я рекурсивно вызываю mergesort для левого массива, я должен наконец получить левую = [4] и после этого я вызываю его для правого массива, который должен стать = [1]

Итак, я должен остаться со слиянием [4] и [1] и он должен вернуть [1,4] в качестве окончательно отсортированной массив. Однако это не так, и код действительно возвращает правильный отсортированный массив.

Есть ли другой способ, которым компилятор интерпретирует этот рекурсивный код? Или я ошибаюсь с тем, что написал выше?

PS: я знаю, что на подобные вопросы здесь даны ответы, но они не имеют отношения к этим конкретным c строкам кода, а скорее дают общее представление сортировки слиянием

Answer 1

Ваша программа выполняется построчно. Вызов функции приостанавливает выполнение текущей функции и ожидает возврата вызванной функции. Когда функция вызывается рекурсивно (даже если это косвенно, где a вызывает b и b вызывает a), вы в основном получаете «новую копию» функции с ее собственными локальными переменными и собственным самостоятельное исполнение. В вашем примере, следующий порядок звонков. Отступы показывают, что функция вызывается функцией на внешнем уровне (которая будет ожидать ее возврата). Обратите внимание, что return не является функцией; вместо этого он останавливает функцию, в которой он находится. Я предполагаю, что в конце mergesort происходит то, что он возвращает результат merge.

mergesort([4, 3, 2, 1])
  mergesort([4, 3])
    mergesort([4])
      return [4] to mergesort([4, 3])
    mergesort([3])
      return [3] to mergesort([4, 3])
    merge([4], [3])
      return [3, 4] to mergesort([4, 3])
    return [3, 4] to mergesort([4, 3, 2, 1])
  mergesort([2, 1])
    exercise: figure out the rest :-)