# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### External Selection

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Sibeyn, J. F. (1999). External Selection. In C. Meinel, & S. Tison (*Proceedings of the 16th Annual Symposium on Theoretical Aspects
of Computer Science (STACS-99)* (pp. 291-301). Berlin: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-35C5-1

##### Abstract

Sequential selection has been solved in linear time by Blum e.a.
Running this algorithm on a problem of size $N$ with $N > M$, the
size of the main-memory, results in an algorithm that reads and
writes $\go{N}$ elements, while the number of comparisons is also
bounded by $\go{N}$. This is asymptotically optimal, but the
constants are so large that in practice sorting is faster for
most values of $M$ and $N$.
This paper provides the first detailed study of the external
selection problem. A randomized algorithm of a conventional type is
close to optimal in all respects. Our deterministic algorithm is
more or less the same, but first the algorithm builds an index
structure of all the elements. This effort is not wasted: the index
structure allows the retrieval of elements so that we do not need a
second scan through all the data. This index structure can also
be used for repeated selections, and can be extended over time. For
a problem of size $N$, the deterministic algorithm reads $N + o(N)$
elements and writes only $o(N)$ elements and is thereby optimal to
within lower-order terms.