1 Introduction
1.1 Model of Computation
1.2 Results
1.3 Preliminaries and Notation
1.4 Outline of Paper
2 Lower Bound
3 Internal-Memory and External-Memory Multiple Selection
3.1 Internal Memory
3.2 External Memory
3.3 Analysis
4 Cache-Oblivious Multiple Selection
4.1 Funnelsort
4.2 Funnels for Partitioning
4.3 Selecting Pivots
4.4 Truncated Partitioning
4.5 Funnelselect
5 Analysis
6 Partial Sorting
7 Allowing Identical Elements
8 Conclusion and Open Problems