как работает сортировка слиянием.

[DenisVASI]

Здравствуйте не могу понять как работает сортировка слиянием. Я уже прочитал достаточно материалов по ней.В теории мне все ясно. Но как работает это на уровне кода не совсем понимаю.
Вот сам код:

Код: (python) [Выделить]

C = [5, 2, 4, 1, 3, 6]

def merge_sort(A):
    if len(A) <= 1:
        return A
    middle = int(len(A)/2)
    left = merge_sort(A[:middle])
    right = merge_sort(A[middle:])
    return merge(left, right)

def merge(left, right):
    result = []
    while len(left) > 0 and len(right) > 0:
        if left[0] <= right[0]:
            result.append(left[0])
            left = left[1:]
        else:
            result.append(right[0])
            right = right[1:]
    if len(left) > 0:
        result += left
    if len(right) > 0:
        result += right
    return result

print(C)
B = merge_sort(C)
print(B)
Мне в основном ясно как работает Merge, но вот как работает рекурсия в Merge_Sort, в какие моменты она например переключается с left на right, хочу так же уточнить, везде написано что return возвращает значение, но куда он его возвращает. И почему когда возвращается A идет дальнейшее выполнение рекурсивных вызовов, а не завершение функции.
Прошу не посылать в google) уже был там. Объясните пожалуйста

[Azure]

Начнем с return — значение возвращается туда, откуда вызывается функция. Это и позволяет выполнять рекурсию — вызывать функцию "изнутри" самой функции, только уже с полученными внутри параметрами. Так получается несколько уровней вложенности (которые и называют глубиной рекурсии). В Вашем случае будет последовательно вызываться функция Merge_Sort для левой и правой половин списка, пока длина "половинки списка" не окажется равной или меньшей 1, после чего все "уровни" начнут "сворачиваться" в обратном порядке.

[DenisVASI]

Спасибо большое, пошаговый разбор и ваш отзыв дали нужный результат. Оказывается есть такое понятие как глубина рекурсии .Буду читать.