Use a radix sort. Complexity of the radix sort is O(N k) where k is the number of digits used to represent the number in some base b. If we use the convenient fiction that both N and N^2 fit into the same 32 bit integer then k is a constant and we get an O(N) sort. (It's kindof cheating :) ). Okay, since we don't want to cheat on this one, keep reading below: :)
Another method is to divide the Numbers into N bins of size N numbers. Eg. Bin 1 = 1 to N, Bin 2 = N+1 to 2N ... Assuming uniform distribution, the bins will have N/N ~ 1 element each. If the distribution is non-uniform then no bin will have more than N elements. For small bins, apply a variant of insertion sort (which performs faster than O(n log n) sorts for < 12 elements) and if N is large, will perform much faster than counting sort. For large bins, apply an O(n log n) sort or radix sort or counting sort. (make a choice depending on number of elements in the bin. eg. Num_elements ~ N then choose counting sort, else choose radix or O(n log n) sorts) Complexity analysis: 1. No bin will have more than N elements. 2. No bin while being sorted will have a range > N. If the data distribution is uniform, the solution will be very very quick (order of N) as the sorting time for bins with just 2 to 3 elements is approximately O(num_elements) ~ O(1) and number of such bins is O(N). If the data distribution is non-uniform, then complexity will depend on the number of bad bins and the size of bad bins. Let K bins be bad. Here, K is a value dependent on data distribution of the input. If K is small, number of elements per bin is large -> apply counting sort on the bins -> complexity O(K N) which is approximately O(N) If K -> log N, apply an O(N log N) sort to the bins -> complexity O( K * N/K log (N/K)) -> O(N log (N/log N)) If K > log N but K < N, worst case -> complexity Sum over K bins{min{O(Ni log (Ni)), O(N)}} (you can cheat this to O(N) by using something like radix sort) If K -> N -> Not possible as you won't have that many bad bins as the number of elements per bin will approach 1. So, in short, you can get a complexity of the kind O(N log (N/log N)) which is slightly better than O(N log N). Hope this helps! -- DK http://twitter.com/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/OCYjpn_zkigJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.