Random commentary about C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Use IntroSort (http://en.wikipedia.org/wiki/Introsort)
Introsort - http://en.wikipedia.org/wiki/Introsort
and without going in that direction?
Does parallelizing the operations count as making it better ?
no. seletion counts
OK. Randomized Quick Sort provides you an expected case runtime of O(nlgn). The reason why this is expected as against worst case is that there is always a possibility of picking up a bad pivot regardless of how random your selection is. Thinking is if I can guarantee that my pivot selection will never be the bad one, I can guarantee worst case run time of O(nlgn) for Quick Sort. How can I guarantee that my pivot selection will never be a bad one? Thinking is using something like the "Median of Medians algorithm" to pick the pivot. Would the above be a valid answer?
i like the second one.