• 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