What is the fastest way to sort these n^2 numbers?

Question

Given a number 'n', I want to return a sorted array of n^2 numbers containing all the values of k1*k2 where k1 and k2 can range from 1 to n.

For example for n=2 it would return : {1,2,2,4}.(the number are basically 1*1,1*2,2*1,2*2).

and for n=3 it would return : {1,2,2,3,3,4,6,6,9}.

(the numbers being : 1*1, 2*1, 1*2, 2*2, 3*1, 1*3, 3*2, 2*3, 3*3)

I tried it using sort function from c++ standard library, but I was wondering if it could be further optimized.

Answer 1

Well, first of all, you get n^2 entries, the largest of which will be n^2, and of the possible value range, only a tiny amount of values is used for large n. So, I'd suggest a counting approach:

1. Initialize an array counts[] of size n^2 with zeros.
2. Iterate through your array of values values[], and do counts[values[i]-1]++.
3. Reinitialize the values array by iterating through the counts array, dropping as many values of i+1 into the values array as counts[i] gives you.

That's all. It's O(n^2), so you'll hardly find a more performant solution.