Я прочитал, что для рекурсивной реализации QuickSort потребуется O (log n) дополнительного пространства. С чего бы это?
Это из-за стека?
Да, действительно, это было бы до места в стеке для рекурсивных вызовов.
Это может быть рассмотрено из-за стекового пространства, также в каждой рекурсии вы делите свой массив на две части, что для всего процесса занимает log N времени, что совершенно неизбежно ....
O (log n) - ничто, просто указатели требуют такого количества памяти.