Where this hubris comes from ?
Posted Jan 13, 2012 23:34 UTC (Fri) by khim
In reply to: Worst case performance and "impossibly unlikely" conditions
Parent article: Denial of service via hash collisions
The median of medians, though possibly a useful thing, is not the same thing as the median.
Un·be·liev·a·ble. STFW! The first result gives you link to Median of Medians algorithm - and yes, this algorithm can be used to find median in linear time.
So that's what I was responding to.
The only thing you response shows is that you just refuse to think. First you were given hint: it's possible to find median in linear time (already enough to find the answer). The you were given then name of the algorithm. Yet still you continue to persist in your ignorance. Perhaps direct link will convince you?
Can we, please, close this discussion? Yes, it's possible to find median in linear time and yes, you can make quicksort O(N log N) in the worst case using this approach. No, this is usually not feasible because it adds so many manipulations to quicksort that it stops being quick - if you really wonder about worst case scenarios there are different algorithms.
to post comments)