Selection in the Presence of Memory Faults, with Applications to In-place Resilient Sorting

Tsvi Kopelowitz, Nimrod Talmon

The selection problem, where one wishes to locate the $k^{th}$ smallest element in an unsorted array of size $n$, is one of the basic problems studied in computer science. The main…