3 ms·

Quick sort can be made to be O(n log n) with careful choice of pivot - e.g. https://en.wikipedia.org/wiki/Median_of_medians https://en.wikipedia.org/wiki/Median

by hhmc 7y ago

Quick sort can be made to be O(n log n) with careful choice of pivot - e.g. https://en.wikipedia.org/wiki/Median_of_medians https://en.wikipedia.org/wiki/Median_of_medians

kccqzy 7y ago
Generally it is preferable to choose the pivot randomly.
- hhmc 7y ago
  Sure, and the wikipedia page makes mention of that. But it's not super relevant to the point I'm making about the worst-case complexity of quick sort (which is often misunderstood to be O(n^2)).