There's a well-known order statistic finding algorithm that's O(n) worst case. See Aho, Hopcroft, and Ulman, DACA. This lets you find the k'th element for any k. Use it to find the log n'th student and the sqrt n'th student and then one final O(n) pass to partition the group will do the job.
-- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
