Нижняя граница Ω(nlogn) временной сложности каждого алгоритма сортировки на основе сравнения при заданном максимуме M

Это не влияет.

Обратите внимание, что существует n! возможная перестановка, и каждая операция сравнения имеет 2 возможных результата: «левый выше» или «правый выше».
Для любого алгоритма, основанного на сравнениях, каждое «решение» принимается в соответствии с результатом одного сравнения.

Таким образом, чтобы успешно определить правильный порядок любой перестановки, вам понадобится (в худшем случае) log₂(n!) сравнений.
Однако хорошо известно, что log₂(n!) находится в тета(nlogn) – и вы вернулись к нижней границе Omega(nlogn), независимо от диапазона в рука.

Обратите внимание, что другие методы, которые не используют (только) сравнения, существуют для более эффективной сортировки целых чисел.

Если M действительно является границей абсолютных значений элементов массива, а элементы являются целыми числами, вы можете отсортировать массив за O(n + M) времени, сохранив отдельный массив int occurrences[2M + 1]; инициализированным до 0, просмотрев исходный массив и подсчитав число вхождений каждого элемента и запись выходного массива с использованием occurrences.

Если элементы являются числами с плавающей запятой (формально вещественными числами), ограничение их величин не имеет никакого эффекта.

Если элементы являются целыми и могут быть отрицательными (формально целыми числами сколь угодно большой величины), то верхняя граница величин не имеет значения.

Изменить: в первом абзаце было O(n), должно быть O(n + M).