We have 100 000 fractions: Let's consider following fractions. p/(2^q) such that 0 <= p,q <= 10
As you can see there are <= 10 * 10 different fractions, but we have 100 000 that we have to sort them (so there are little unique elements).
Task is about thinking fast algorithm to sort fractions.
I ask you for looking at my proposition and show me your ideas. (I assume that fractions are given by pair, for instance: p/q <----> (p, q) ) on input we have array a
for i = 1 to n do t[i] = a[i].first * 2^(10) countsort (t) bring results from t to a (remember about / 2^10)