Question: consider the problem of sorting n elements, where the oracle of comparison is allowed to lie no more than once during the execution of the algorithm. Difficulty is measured in terms of the number of comparisons (consultation of oracles). Show how to sort n elements in this model using only nlgn + O (n) comparisons, providing your algorithm and proof of correctness.
What I have:
My best solution is still pretty rudimentary. I basically implement a merge sort form, where only the difference when comparing merge, I compare two times (since the oracle can only lie once, if there is a mismatch I will compare the third time, but this can only happen once).
I know that there are lg (n) merge levels, and that since I have n elements, the maximum number of comparisons that I will make is 2nlg (n) +1. However, this is a pretty rough upper bound, since I know that merging two arrays of length m and p takes m + p-1 comparisons (not m + p).
For simplicity, if I assume that the lengths of the array are of degree 2, I have m = p, and I get the total number n-1. So I can subtract 2 (n-1) from 2nlg (n) +1, which gives me 2nlg (n) - 2n - 1 comparisons.
Not the answer I'm looking for. I think I'm wrong (I don’t think I need to compare twice every time I merge ..), and I would be very grateful if someone could push me in the right direction!
Greetings
Sacha