О сложности самокорректирующихся алгоритмов для двух задач сортировки

Для стандартной задачи сортировки $n$-элементного множества получен оптимальный по порядку алгоритм, корректирующий не более $k(n)$ ошибочных сравнений элементов сортируемого множества. Показано, что этот алгоритм асимптотически оптимален при $k=o(\log n)$. Оптимальный по порядку самокорректирующийся алгоритм получен также для задачи сортировки множества, изоморфного булевой алгебре.