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

В конце работы имеем отсортированный массив.