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 + δ√n log n) expected time and its deterministic variation that runs in O(n log n +δ√n log n) worst-case time. This improves the previous known result for δ >√n log n. Our deterministric sorting relies on the notion of an approximate kth order statistic. For this auxiliary problem, we devise a deterministic algorithm that runs in O(n + δ√n) time and produces a key (either corrupted or not) whose order rank differs from k by at most O(δ).