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

QUICKSORT(A, p, r)
       q = PARTITION(A, p, r)
       QUICKSORT(A, p, q-1)
       QUICKSORT(A, q+1, r)


TAIL-RECURSIVE-QUICKSORT(A, p, r)
   while p < r
      q = PARTITION(A, p, r)
      TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
      p = q+1

(Источник -http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html)

Насколько я понимаю, оба они вызовут рекурсивные вызовы как в левой, так и в правой половине массива. В обоих случаях только одна половина будет обрабатываться одновременно, и поэтому в любое время только один рекурсивный вызов будет использовать пространство стека. Я не могу видеть, как рекурсивная быстрая сортировка хвоста экономит место.

Псевдокод выше взят из статьи -http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html Объяснение, приведенное в статье, смущает меня еще больше -

Быстрая сортировка разделяет заданный под-массив и перерабатывается дважды; один слева-под-массив и один справа. Каждый из этих рекурсивных вызовов потребует отдельного потока стекового пространства. Это пространство используется для хранения индексных переменных для массива на некотором уровне рекурсии. Если мы представим, что это происходит от начала до конца выполнения, мы можем видеть, что пространство стека удваивается на каждом уровне.

Так как же Tail-Recursive-Quicksort все это исправляет?

Что ж, вместо рекурсии на двух подмассивах, теперь мы рекурсируем только на одном. Это устраняет необходимость удваивать пространство стека на каждом уровне выполнения. Мы можем обойти эту проблему, используя цикл while в качестве итеративного элемента управления, который выполняет ту же задачу. Вместо того, чтобы использовать стек для сохранения наборов переменных для двух рекурсивных вызовов, мы просто изменяем один и тот же набор переменных и используем один рекурсивный вызов для новых переменных.

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

Примечание: - В статье нет упоминаний об оптимизации компилятора.