Нижняя граница для сортировки n значений в диапазоне от 1 до k на основе сравнения

Можем ли мы добиться большего, чем O (n lg n) времени работы для алгоритма на основе сравнения, когда все значения находятся в диапазоне от 1 до k, где k

Сортировка с подсчетом и сортировка по основанию счисления не являются алгоритмами, основанными на сравнении, и их использование запрещено. Анализ дерева решений показывает, что существует k ^ n возможных перестановок. Количество листов составляет 2 ^ ч, поэтому проблема должна быть решена за время O (n lg k) с помощью алгоритма сортировки, основанного на сравнении .

Пожалуйста, не указывайте не основанный на сравнении Алгоритм сортировки для решения этой проблемы, вся сортировка должна основываться на сравнении двух элементов. Спасибо!