2017/09/21 by Barbara Geissmann, Geissmann, Barbara, Stefano Leucci +5 · 1 citation
Computer Science · Decision Sciences · Mathematics · #Bayesian Methods and Mixture Models #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Probability and Risk Models #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.1709.07249
openalex publication_date 2017/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a sorting algorithm for the case of recurrent random comparison errors. The algorithm essentially achieves simultaneously good properties of previous algorithms for sorting n distinct elements in this model. In particular, it runs in O(n2) time, the maximum dislocation of the elements in the output is O(log n), while the total dislocation is O(n). These guarantees are the best possible since we prove that even randomized algorithms cannot achieve o(log n) maximum dislocation with high probability, or o(n) total dislocation in expectation, regardless of their running time.