Lower bound Ω(nlogn) of time complexity of every comparison based sorting algorithm given M maximum

Question

Given the maximum element M of array with n elements [1,...,n], how the lower bound Ω(nlogn) of time complexity of every comparison based sorting algorithm is affected? I must highlight that the maximum element M of the array is given.

Answer 1

It is not affected.

Note that there are n! possible permutation, and each compare OP has 2 possible outcomes - 'left is higher' or 'right is higher'.
For any comparisons based algorithm, each 'decision' is made according to the outcome of one comparison.

Thus, in order to successfully determine the correct order of any permutation, you are going to need (at worst case) log₂(n!) comparisons.
However, it is well known that log₂(n!) is in Theta(nlogn) - and you got yourself back to a lower bound of Omega(nlogn), regardless of the range at hand.

Note that other methods that do not use (only) comparisons exist to sort integers more efficiently.

Answer 2

If M is really a bound on the absolute values of the elements of the array, and the elements are integers, you can sort the array in O(n + M) time, by keeping a separate array int occurrences[2M + 1]; initialized to 0, scanning your original array and counting the number of occurrences of each element, and writing the output array using occurrences.

If the elements are floats (formally, real numbers), having a bound on their magnitudes has no effect.

If the elements are integral and can be negative (formally, integers of arbitrarily large magnitude), then having an upper bound on the magnitudes has no effect.

Edit: had O(n) in first paragraph, should be O(n + M).