Give a linear-time algorithm to sort the ratios of n given pairs of integers between 1 and n. I.e., we need to sort, within O(n) time, n pairs of the form (ai , bi) where 1 ≤ ai ≤ n and 1 ≤ bi ≤ n using the sort key ai bi . Prove both run-time and correctness.
