Wikipedia lists the median-of-medians algorithm as requiring O(1) auxiliary space.
However, in the middle of the algorithm, we make a recursive call on a subarray of size n/5 to find the median of medians. When this recursive call returns, we use the returned median of medians as a pivot to partition the array.
Doesn't this algorithm push O(lg n) activation records onto the run-time stack as a part of the recursion? From what I can see, these recursive calls to find successive medians of medians cannot be tail-call optimized because we do extra work after the recursive calls return. Therefore, it seems like this algorithm requires O(lg n) auxiliary space (just like Quicksort, which Wikipedia lists as requiring O(lg n) auxiliary space due the space used by the run-time stack).
Am I missing something, or is the Wikipedia article wrong?
(Note: The recursive call I'm referring to is return select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10) on the Wikipedia page.)
While I can't rule out that O(1) is possible, that Wikipedia information appears to be a mistake.