Нужна помощь, чтобы обернуть голову вокруг типа реализации быстрой сортировки

Question

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

Как работает функция «вернуть быструю сортировку (меньшую) + равную + быструю сортировку (большую)»? Если quicksort () вызывается рекурсивно, то не будут ли очищаться всегда меньшие, равные и большие массивы при инициализации функции каждый раз? Как именно Python запоминает организованный массив? Как Python знает, как остановить эту рекурсию?

источник кода: Быстрая сортировка с Python

def quicksort(array):
    lesser = []
    equal = []
    greater = []

    if len(array) > 1:
        p = array[0]
        for x in array:
            if x < p:
                lesser.append(x)
            elif x == p:
                equal.append(x)
            elif x > p:
                greater.append(x)

        return quicksort(lesser)+equal+quicksort(greater) # ???

    else:
        return array

Answer 1

Рекурсия создает новые экземпляры функции, включая переменные, в памяти ( кадр стека ).Правильно, что эти списки очищаются функцией, но не в начальном экземпляре.Функция рекурсивно создает новые ветви и закроет начальный экземпляр только после того, как последующие экземпляры завершат, закроют и вернут свой вклад.

Answer 2

Функция создает 3 новых массива каждый раз, когда она вызывается.Хотя они имеют одно и то же имя, они на самом деле различны, потому что рекурсивный вызов помещает все локальные данные функции в стек (а не только параметры).

Таким образом, 3 массива из предыдущего вызова не теряются при вызове самой функции.