Vi anser att problemet med att sortera n-element vid ihållande jämförelsefel är problematiskt. I denna modell (Braverman och Mossel, SODA'08) kan varje jämförelse mellan två element vara fel med vissa fasta (små) sannolikhet p, och jämförelser kan inte upprepas. Att sortera perfekt i denna modell är omöjligt, och målet är att minimera förskjutningen av varje element i utdatasekvensen, det vill säga skillnaden mellan dess verkliga rang och dess position. Befintliga lägre gränser för detta problem visar att ingen algoritm kan garantera, med hög sannolikhet, maximal dislokation och total dislokation bättre än (log n) respektive (n), oavsett dess körtid. I detta dokument presenterar vi den första O(n log n)-tidssorteringsalgoritmen som garanterar både O(log n) maximal dislokation och O(n) total dislokation med hög sannolikhet. Förutom att förbättra över de tidigare toppmoderna algoritmer - den mest kända algoritmen hade körtid Õ(n 3/2 ) - vårt resultat indikerar att jämförelsefel inte gör problemet beräknings svårt: en sekvens med bästa möjliga dislokalisering kan erhållas i O(n log n) tid och, även utan jämförelsefel,  på tid (n log n) krävs för att garantera sådana dislokation gränser. För att uppnå detta optimala resultat löser vi två delproblem, och respektive metoder har sina egna meriter för vidare tillämpning. En är hur man lokaliserar en position där man infogar ett element i en nästan sorterad sekvens med O(log n) maximal dislokation på ett sådant sätt att dislokaliseringen av den resulterande sekvensen fortfarande kommer att vara O(log n). Den andra är hur man samtidigt infoga m element i en nästan sorterad sekvens av m olika element, så att den resulterande sekvensen av 2m element förblir nästan sorterade.
Det har visats till exempel i REF, att det finns en algoritm med körtid O(n log n) som uppnår samtidigt maximal dislokation O(log n) och total dislokation O(n) med hög sannolikhet, och att detta verkligen är den bästa man kan hoppas på (dvs. det finns matchande lägre gränser som visar att ingen möjligen randomiserade algoritm kan sortera så att, med hög sannolikhet, den maximala dislokeringen är o(log n) eller den totala dislokationen är o(n)).
Optimal Sorting with Persistent Comparison Errors
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}