# Sorting rational numbers in linear time

I am currently studying algorithms and computational complexity at University.

I have recently got through three questions I found in an old exam:

1. Is it possible to sort in asymptotically linear time an array of rational numbers between $$[1, 1.5]$$ with limited numerator?

2. Is it possible to sort in asymptotically linear time an array of rational numbers between $$[0, 0.5]$$ with limited numerator?

3. Is it possible to sort in asymptotically linear time an array of rational numbers between $$[0, 100]$$ with limited denominator?

First of all I tried to understand what the author meant with "limited": I assumed it to be a synonym of "fixed" (i.e. a generic value $$k$$) and what comes below is based on this assumption.

As far as I know we can use three algorithms to achieve $$O(n)$$: counting sort, radix sort and bucket sort. In these questions no uniform distributions are guaranteed, so I basically ignored the last one.

For (1) I thought this: if all the numerators are the same ($$k$$), then we only have to sort all the elements by their denominator, in reverse order. Since the range is $$[1, 1.5]$$, the denominators must be an integer between $$\left[\left\lceil\frac{2}{3}k\right\rceil, k\right]$$. That is a limited interval of integers, so we can use counting sort and get $$O(n)$$. The answer is indeed "true", as stated in the solution.

For (2) I tried a similar approach: in this case we have a lower bound of $$0$$, so to reach it with a $$k$$ numerator we would need an infinite denominator. Since counting sort requires a finite range, we conclude that we can't get $$O(n)$$. The solution says "false", as I did.

For (3) we have a little difference but my intuition was to apply the same reasoning: if we set $$k$$ as denominator, then we must have a numerator in $$[0, 100k]$$ to fit within the original range. A fixed interval: we can apply counting sort! But the answer in the solution this time is "false", we do not sort in linear time.

The only other difference compared to (1) and (2) is the upper bound, which is higher. So, if we had a very large $$k$$, the range would be even larger and in $$O(n + k)$$ it would dominate over $$n$$. Anyway, I found another exam paper in which the range is completely removed, and the answer keeps to be marked as false.

I repeat: I based all of the above on the original assumption. I ask, therefore: was it wrong? Does "limited" have another meaning in this context? Or, more in general: why can't (3) be sorted in linear time, while (1) can?