Really really sorry for polluting this thread, but there's small issue in that analysis: The cost O(N) is in terms of reverse operations executed (that is swaps) and not in terms of the number of comparisons. The number of comparisons remain O(N log N) but the maximum number of swaps is O(N) which would be of the same order as quicksort. :(
Sorry for the multiple posts guys. It's 4 am and my mind's not that sharp right now. :( -- DK -- 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/-/hSOI1KGgt9kJ. 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.
