Selection from read-only memory with limited workspace

Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen +1

Given an unordered array of $N$ elements drawn from a totally ordered set and an integer $k$ in the range from $1$ to $N$, in the classic selection problem the task is to find the…