Problem solving

I have already told in the introduction about myself, my blogs can be random...well, I mean, with a probability (P) of any topic being covered defined as
P = a rational number x where 0 <= x <= 1 ;)

So, let's solve a algorithmic problem, which I found on someone else' blog (http://my-experiments-with-it.blogspot.com) and liked it.

Here goes it:

You have an array of size 'n' with numbers from 1 to 'n'. You need to sort this array in the most optimal way.

HINT(Don't read the hint if you think you can do without it): The solution has a complexity of O(n). i.e. even less than the O(n.log(n)) which is given by the best sorting algorithms.

Find the answer in the comments section.