I think count sort is not acceptable (see Ankur's post for
explanation), while radix sort fits the requirement.
Take the array as an array of 2-digit base n numbers.
First sort by the least significant digit (x%n), then the most
significant digit (x//n), both using the stable counting sort. The
overall time complexity is O(n).
On 2010-8-2 17:34, Avik Mitra wrote:
You can use count sort or radix sort. Both are of O(n) as running time
complexity.
You can refer to the book by "Introduction to Algorithms" by Thomas H.
Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to algoge...@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.
