On May 21, 7:17 am, Bharath <bharath1...@gmail.com> wrote: > Find the median of the values and move the lower values to left and higher > values to the right. This can be done in o(n). now do the same on both the > parts recursively. And the total complexity will be o(nlogk). >
Very good! I never thought of this even though I knew you could make quicksort be O(n log(n)) by using the the median as the pivot point. Of course I'm sure everyone realizes that one needs to stop the recursion when all the elements in a subarray are the same. Regards, Ralph Boland -- 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.