Я придумал однопроходную сортировку с линейной сложностью O(n). Я назвал ее Сталинская сортировка. Проходим по каждому элементу проверяя находится ли элемент на своем месте или нет. Если элемент не на своем месте то просто его уничтажаем. В конце имеем отсортированое множество.