Доброго Нового Года!
В копилку экзотических способов сортировки предложу еще один, немного своеобразный, но обещающий приличную скорость при хорошо случайных данных.
Пусть имеется набор N из n целых положительных чисел от 1 до n.
Самоочевидно, что для хранения n чисел необходимо иметь n ячеек. Вне зависимости от порядка, в котором числа будут записаны.
Исходный массив
| 3 | 5 | 2 | 1 | 8 | 4 | 7 | 6 | 9 | 10 |
Несложно представить, что неупорядоченный набор N достаточно просто заменить упорядоченным (по возрастанию, или по убыванию), записав упорядоченный набор на место неупорядоченного.
Упорядоченный массив
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
