Resilient Quicksort and Selection

We consider the problem of sorting a sequence of

n

keys in a RAM-like environment where memory faults are possible. An algorithm is said to be

δ-resilient

if it can tolerate up to

δ

memory faults during its execution. A resilient sorting algorithm must produce a sequence where every pair of uncorrupted keys is ordered correctly. Finocchi, Grandoni, and Italiano devised a

δ

-resilient deterministic mergesort algorithm that runs in

O

(

n

log

n

 + 

δ

2

) time. We present a

δ

-resilient randomized algorithm (based on quicksort) that runs in

$O(n \log n + \delta \sqrt{n \log n})$

expected time and its deterministic variation that runs in

$O(n \log n + \delta \sqrt{n} \, \log n)$

worst-case time. This improves the previous known result for

$\delta > \sqrt{n} \, \log n$

.

Our deterministric sorting relies on the notion of an approximate

k

-th order statistic. For this auxiliary problem, we devise a deterministic algorithm that runs in

$O(n + \delta \sqrt{n})$

time and produces a key (either corrupted or not) whose order rank differs from

k

by at most

O

(

δ

).