Thanks for the link. Note, though, that the median algorithm used there uses a different parameter for n than OP. It also is bucketsort-based and O(n), O(1) only amortized (in both parameters).
Additional knowledge of your data is often useful, like using the fact that all data are 8-bit integers above. Similarly, if you know your data is uniformly distributed, you could try Torben (in TFA) for pivot selection in quickselect.
Comments
Thanks for the link. Note, though, that the median algorithm used there uses a different parameter for n than OP. It also is bucketsort-based and O(n), O(1) only amortized (in both parameters).
Additional knowledge of your data is often useful, like using the fact that all data are 8-bit integers above. Similarly, if you know your data is uniformly distributed, you could try Torben (in TFA) for pivot selection in quickselect.