Оптимизировать поразрядную сортировку для граничных случаев

[izvolov]

1. Часто сортируются многоразрядные числа (например, int64), но при этом диапазон значений по факту небольшой (например, [0—1000]). В этом случае старшие разряды всех чисел равны, и сортировать по ним не нужно. В этом случае скорость сортировки увеличится. Необходимость сортировки по разряду можно понять из состояния счётчиков этого разряда.
2. У нас нет порядка на сортируемых значениях, есть только отображение в целые числа. Но на целых числах порядок есть всегда. Это можно использовать: при сборе счётчиков проверить порядок на образах изначальных элементов, и если образы упорядочены, то и изначальные числа — тоже. В этом случае сортировать вообще не нужно.