Optimal Time Minimal Space Selection Algorithms
David Dobkin, J. Ian Munro · Journal of the ACM · 1981
Algorithms for findmg medians and solving arbitrary selection problems using a minimum number of data storage locations are investigated A linear-tmle algorithm is given in the first case, and it ~s shown that no such scheme exists for many other interesting selection problems, such as finding a quartile A right trade-off is demonstrated balancing extra space versus time.