Какой самый эффективный способ использовать компаратор для сортировки, если компаратор прав, скажем, 80% времени? А компаратор это черный ящик, т.е. Вы не можете явно преобразовать C: (a, b) -> [- 1,0,1] в некоторую оценку: (a) -> функцию оценки R элементов. В основном, оценка - это то, что мы пытаемся установить, используя этот неисправный компаратор.
Наивное решение: сравнить все элементы со всеми другими элементами. Каждый элемент будет связан с выходами компаратора N-1. Суммируйте их за элемент, то есть за элемент. Но я не уверен, что это эффективно. Я надеялся, что есть какой-то академический ответ на эту проблему.