References
- Blum , M. , Floyd , R. W. , Pratt , V. R. , Rivest , R. L. and Tarjan , R. E. 1973 . Time bounds for selection . J. Comput. Syst. Sci. , 7 : 448 – 461 .
- Kirkpatrick , D. G. 1981 . A unified lower bound for selection and set partitioning problems . J. ACM , 28 : 150 – 165 .
- Knuth , D. E. 1969 . The Art of Computer Programming , Vol. I , Reading, MA : Addison-Wesley . Fundamental Algorithms
- Schonhage , A. , Paterson , M. and Pippenger , N. 1976 . Finding the median . J. Comput. Syst. Sci. , 13 : 184 – 199 .
- Hyafil , L. 1976 . Bounds for selection . SIAM J. Comput. , 5 : 109 – 114 .
- Munro , J. I. and Poblete , P. V. 1982 . “ A lower bound for determining the median ” . Canada : University of Waterloo . Res. Rep. CS-82-21
- Floyd , R. W. and Rivest , R. L. 1975 . Expected time bounds for selection . Commun. ACM , 18 : 165 – 172 .
- Cunto , W. and Munro , J. I. Average case selection. In: . Proceedings of the 16th Annual ACM Symposium on Theory of Computing . 1984 . pp. 369 – 375 . Washington : ACM Press) .
- Gerbessiotis , A. V. and Siniolakis , C. J. 2003 . Randomized selection in n+C+o(n) comparisons . Inform. Process. Lett. , 88 : 95 – 100 .
- Gerbessiotis , A. V. and Siniolakis , C. J. Deterministic sorting and randomized median finding on the BSP model . Proceedings of the 8th ACM Symposium on Parallel Algorithms and Architectures . 1996 , Padua, Italy. pp. 223 – 232 .
- Reif , H. J. and Valiant , L. G. 1987 . A logarithmic time sort for linear size networks . J. ACM , 34 : 60 – 76 .
- Gerbessiotis , A. V. and Valiant , L. G. 1994 . Direct bulk-synchronous parallel algorithms . J. Parallel Distrib. Comput. , 22 : 251 – 267 .
- Angluin , D. and Valiant , L. G. 1979 . Fast probabilistic algorithms for Hamiltonian circuits and matchings . J. Comp. Syst. Sci. , 18 : 155 – 193 .
- Bollobás , B. 1984 . Random Graphs , New York : Academic Press .
- Dor , D. and Zwick , U. 1999 . Selecting the median . SIAM J. Comput. , 28 : 1722 – 1758 .
- Dor , D. and Zwick , U. 2001 . Median selection requires (2+ε)n comparisons . SIAM J. Discrete Math. , 14 : 312 – 325 .
- Gerbessiotis , A. V. and Siniolakis , C. J. 1996 . “ Concurrent heaps on the BSP model ” . Computing Laboratory, University of Oxford . Tech. Rep. PRG-TR-14-96
- Knuth , D. E. 1973 . The Art of Computer Programming , Vol. III , Reading, MA : Addison-Wesley . Sorting and Searching