Заметил одну прекрасную сортировку, которая имеет очень интересную идею, хорошо улучшающую алгоритм. Она очень проста и заключается вот в чем:
- мы, грубо говоря, оцениваем примерный индекс каждого элемента
- так как индексы могут повторяться, то запишем их в многомерный массив
- после мы склеим все эти небольшие массивы (только в самом крайнем случае на один индекс будет претендовать более 4 элементов) в один готовый массив
Автор этой сортировки - пользователь Хабр V2008n и написал он свой пост аж в 2014 году! Да мало того, что написал, он показал пример кода, который был написан на Форт, совершенно непонятном для меня. Также я нашел вариант на JS, который уже был более читаем и так я и смог написать этот код Соломоновой сортировки. Сложность алгоритма колеблится от линейной до квадратичной, однако такой относительно хороший результат требует достаточно много памяти из-за инициализации многомерных динамических массивов.