Top k with a deterministically noisy comparator

You must rank items through a comparison function cmp(a, b) that is wrong about 10% of the time, and consistently so: asking about the same pair again gives the same answer. Given n items and k, return the k largest.

1. Say what guarantee you can offer, since repeated calls can't fix a wrong answer.
2. Implement it, for example with a merge sort or tournament over the comparator, and measure how far the result is from the true order.
3. Discuss making it more robust, such as counting wins over many pairwise comparisons, and what the extra comparisons cost.