# An integer array of length N, containing values in the range 1,2,3…N^2. Sort the array in O(N) time

Given N value. So that we can find N^2 value. We can count number of digits in this value.. lets say number of digits is k.
Then apply Radix sort for k times. Order of complexity is O(kN) can be written as O(N).
search for Radix sort if you dont know.

using radix sort with N buckets and two passes. Basically, you treat the numbers as having 2 digits in base N.
Write each integer in base N, that is each x can be represented as (x1, x2) with x = 1 + x1 + x2*N. Now you can sort it twice with counting sort, once on x1 and once on x2, resulting in the sorted array.

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥

http://stackoverflow.com/questions/4238460/an-array-of-length-n-can-contain-values-1-2-3-n2-is-it-possible-to-sort-in
http://en.wikipedia.org/wiki/Radix_sort#Least_significant_digit_radix_sorts