Необходимые площади сортировки с объединением

Я пытаюсь понять необходимые площади для Сортировки с объединением, O (n).
Я вижу, что требования времени в основном, количество уровней (logn) * слияние (n) так, чтобы сделал (n, регистрируют n).
Теперь, мы все еще выделяем n на уровень, в 2 различных массивах, левых и правых.
Я действительно понимаю, что ключ здесь - то, что, когда рекурсивные функции возвращаются, пространство освобождено, но я не вижу его слишком очевидный.
Кроме того, вся информация, которую я нахожу, просто указывает, что требуемое пространство является O (n), но не объясняйте это.
Какая-либо подсказка?

function merge_sort(m)
    if length(m) ≤ 1
        return m
    var list left, right, result
    var integer middle = length(m) / 2
    for each x in m up to middle
         add x to left
    for each x in m after middle
         add x to right
    left = merge_sort(left)
    right = merge_sort(right)
    result = merge(left, right)
    return result

ОТРЕДАКТИРУЙТЕ хорошо благодаря @Uri, это - прием
То, что мне не удалось видеть в самом начале, - то, что время только добавляет, в то время как память добавляет и вычитает, таким образом, максимальное количество времени в конце выполнения, но максимальный объем памяти у основания рекурсивного стека.

Так, если мы продолжаем добавлять n + n/2 + n/4 + n/8.... не имеет значения, сколько раз мы добавляем, это никогда не будет больше, чем 2n, и когда мы достигнем рекурсивного дна стека и начинаем подниматься, мы не сохраняем память используемой для предыдущего ответвления, таким образом, в макс., 2n был бы используемый объем памяти, O (n).