Robustness versus Performance in Sorting and Tournament Algorithms

In this paper we analyze the robustness of sorting and tournament algorithms against faulty comparisons. Sorting algorithms are differently affected by faulty comparisons depending on how comparison errors can affect the overall result. In general, there exists a tradeoff between the number of comparisons and the accuracy of the result, but some algorithms like Merge Sort are Pareto-dominant over others. For applications, where the accuracy of the top rankings is of higher importance than the lower rankings, tournament algorithms such as the Swiss System are an option. Additionally, we propose a new tournament algorithm named Iterated Knockout Systems which is less exact but more efficient than the Swiss Systems.