Median Of Medians Space Complexity

I implemented an nth_number selection algorithm using Medians of Medians. On wikipedia, it states that it's space complexity is O(1) I had to store the medians in a temporary arra

Solution 1:

The selection algorithm needs to rearrange the input vector, since it does a series of partitions. So it's reasonable to assume that it is possible to rearrange the input vector in order to find the median.

One simple possible strategy is to interleave the groups of five, instead of making them consecutive. So, if the vector has N == 5K elements, the groups of five are:

(0,   k,    2k,   3k,   4k)
(1,   k+1,  2k+1, 3k+1, 4k+1)
(2,   k+2,  2k+2, 3k+2, 4k+2)
...
(k-1, 2k-1, 3k-1, 4k-1, 5k-1)

Then when you find the median of a group of five, you swap it with the first element in the group, which means that the vector of medians will end up being the first k elements of the rearranged vector.