Новый однопроходный O(n) алгоритм сортировки под названием StalinSort — пробегаешь по массиву и проверяешь каждый элемент, если он не по порядку, то он объявляется предателем и удаляется. В итоге получаем отсортированный массив.

А это github с реализацией этого алгоритма на всех популярных языках программирования
https://github.com/gustavo-depaula/stalin-sort