Как функция слияния вызывает функцию merge_sort? - PullRequest
Новая
       3

Как функция слияния вызывает функцию merge_sort?

1 голос
/ 31 марта 2020 
def merge_sort(items):
  if len(items) <= 1:
    return items

  middle_index = len(items) // 2
  left_split = items[:middle_index]
  right_split = items[middle_index:]

  left_sorted = merge_sort(left_split)
  right_sorted = merge_sort(right_split)

  return merge(left_sorted, right_sorted)

def merge(left, right):
  result = []

  while (left and right):
    if left[0] < right[0]:
      result.append(left[0])
      left.pop(0)
    else:
      result.append(right[0])
      right.pop(0)

  if left:
    result += left
  if right:
    result += right

  return result

unordered_list1 = [356, 746, 264, 569, 949, 895, 125, 455]

ordered_list1 = merge_sort(unordered_list1)

Я понял, когда функция merge_sort() вызывается в первый раз, когда она вызывает себя рекурсивно, пока не останутся только отдельные элементы, а затем при возврате снова вызовет функцию merge(), которая вернет упорядоченный подсписок, но как тогда функция merge_sort () вызывает себя, чтобы перейти на следующий элемент? Я попытался визуализировать код, но застрял, когда оператор return merge(left_sorted, right_sorted) снова переходит на запуск merge_sort().

Может кто-нибудь объяснить, как return merge(left_sorted, right_sorted) снова вызывает merge_sort() после того, как в первый раз возвращается упорядоченный подсписок.

Ответы [ 2 ]

0 голосов
/ 01 апреля 2020

Может ли кто-нибудь объяснить, как return merge(left_sorted, right_sorted) снова вызывает merge_sort() после того, как в первый раз возвращается упорядоченный подсписок.

merge не вызывает merge_sort(), это объединяет два отсортированных подсписка в отсортированный список.

Только merge_sort() вызывает себя рекурсивно, разбивая свой аргумент списка на левую и правую части, пока он не будет сведен к одному элементу. За каждым набором рекурсивных вызовов следует фаза слияния, когда отсортированные подсписки объединяются в отсортированный подсписок, возвращаемый вызывающей стороне ...

0 голосов
/ 31 марта 2020

Может ли кто-нибудь объяснить, как функция return merge (left_sorted, right_sorted) снова вызывает merge_sort () после того, как в первый раз возвращается упорядоченный подсписок.

Поскольку предыдущий экземпляр вызова вызывается merge_sort () все еще находится в стеке. Использование отступа для отображения вложенности вызовов, для простого примера из 4 элементов: 

ordered_list = call merge_sort(items{0 .. 3})
    left_sorted  = call merge_sort(left_split = items{0..2})
        left_sorted  = call merge_sort(left_split  = items{0}) // base case
        right_sorted = call merge_sort(right_split = items{1}) // base case
        return merge(left_sorted, right sorted)
    right_sorted = call merge_sort (right_split = items{2..3})
        left_sorted  = call merge_sort(left_split  = items{2}) // base case
        right_sorted = call merge_sort(right_split = items{3}) // base case
        return merge(left_sorted, right sorted)
    return merge(left_sorted, right sorted)
...