What is a sorting algorithm that is robust to a faulty comparison?

Question

I want to sort a list of n items with a comparison sort. However, one of the comparisons made by the algorithm will be flipped from what it's supposed to be. Specifically, there is one pair of items for which the comparator function consistently gives the wrong result.

What is a efficient n*log(n) sorting algorithm that will be robust to this faulty comparison? By robust, I mean that every item is off by at most k spots from its true position, for some reasonably small k.

If possible, I'd like it to be robust in the worst case (faulty comparison chosen adversarially), but I'll settle for robust in the average case.

An example robust algorithm (that's not efficient), would be to make all n*(n-1)/2 pairwise comparisons, and place each item by how many of the comparisons they won. Then, no matter what comparison the adversary makes, each items index will be off by no more than k=1.

An example of a NON-robust algorithm is quicksort, because the adversary could just choose the largest item to be on the wrong side of the first pivot, making it on average n/2 spots off from its correct index.

Answer 1

I think I've thought up a solution.

First, do a first pass with any decent sorting algorithm you want (like quicksort), which should, at worst, result in only one item that's significantly far from where it should be.

Then, choose a width h that's at least 5.

for i from 0 to n-h, we look at the group of h items at i, i+1, ..., i+h-1. We make all h*(h-1)/2 pairwise comparisons in that group, and rearrange them by who won the most comparisons. We then increment i and move onto the next group.

Afterwards, we do the same thing, but going backwards from i=n-h to i=0.

These two extra passes will bubble up/bubble down the displaced item to be in the correct area, and uses the extra comparisons in a group of h to override the faulty single comparison.

The final number of comparisons will be O(n*log(n)) + n*h*(h-1)/2. Not sure how much better you can do.

This method also works (I think) for more than one faulty comparison. All you need to do is make sure that h is large enough to override those faulty comparisons.

Answer 2

It seems that this tends to be referred to as "noisy" comparison / information rather than faulty.

This paper specifically analyzes various sorting algorithms "robustness" in the context of faulty comparisons and shows both how it affects time/comparisons and the accuracy of the final result. According to their results, merge and quick sorts are the best traditional sorting algorithms. A swiss tournament gives better results, which makes sense since tournament systems are generally designed around the idea of imperfect comparisons. They get the best results from their own algorithm, which appears to be essentially tournament sort.

Sorting from Noisy Information may also be of interest.

Answer 3

If I give you an additional hint, that the two items that are consistently compared incorrectly are adjacent in the correctly sorted array, and I’ve sorted the array for you already so that only these two items are not correctly sorted, then there is no way for you to find out which pair is ordered incorrectly.

Another observation: If the array looks correctly sorted, that is $a_1 < a_2 < ... < a_n$, and A, B are the two values that are consistently compared incorrectly, then either A, B are adjacent (but in the wrong order) in the sorted array and it is impossible to find out which array elements are A and B, or the array is correctly sorted.

If you sort the array using Quicksort with O (n log n) comparisons, and only one of the n^2 / 2 comparisons gives the wrong result, then it is highly likely (some constant times log n / n) that all comparisons gave the correct result, and therefore the array is correctly sorted. In every partitioning, unless you took A or B as the pivot then the partition step is done correctly, the sub-partitions are created correctly.

If say A is the pivot, and B is within the partition, then B will be moved into the wrong sub-partition. Say A < B. B should go into the right sub-partition but goes into the left one instead. If we are very unlucky, then A is also (correctly) in the left sub-partition, later B is picked as a pivot, and A is moved (incorrectly) to the right sub-partition of the left partition. So there is a small chance of B ending up in the wrong place, and an even smaller chance of both A and B ending up in the wrong place.

PS. How you can go wrong...

Assume we have $a_1 < a_2 < a_3 < ... < a_n$, and A and B are the two numbers that are compared incorrectly. Clearly each comparison is correct and the array sorted unless A and B are adjacent in the array. If we have say $a_k < A < B < a_{k+3}$, when in reality A > B, then it is possible that $A > a_{k+3}$ and $B < a_k$, so having an array that looks sorted doesn't mean much at all.

However, if we also have $B > a_k$ and $A < a_{k+3}$ then we have indeed A and B between $a_k$ and $a_{k+3}$ and the array cannot be distinguished from a correctly sorted array.