Википедия перечисляет алгоритм медианы медиан как требующийO(1) вспомогательное пространство.

Тем не менее, в середине алгоритма мы делаем r, ecursive вызов для подмассива размераn/5 найти медиану медиан. Когда этот рекурсивный вызов возвращается, мы используем возвращенную медиану медиан как опору для разделения массива.

Разве этот алгоритм не подталкиваетO(lg n) записи активации в стек времени выполнения как часть рекурсии? Из того, что я вижу, эти рекурсивные вызовы, чтобы найти последовательные медианы, не могут быть оптимизированы с помощью хвостового вызова, потому что мы выполняем дополнительную работу после возврата рекурсивных вызовов. Таким образом, кажется, что этот алгоритм требуетO(lg n) вспомогательное пространство (так же, как Quicksort, который Википедия перечисляет как требующийO(lg n) вспомогательное пространство из-за пространства, используемого стеком времени выполнения).

Я что-то упустил или статья в Википедии неправильная?

(Примечание: рекурсивный вызов, на который я ссылаюсь,return select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10) на странице Википедии.)