6 ms·
Introsort, which used by the C++ standard libraries, switches from quicksort to heapsort for the (sub)partition for which has exceeded the expected recursion de
by gpderetta 7y ago
Introsort, which used by the C++ standard libraries, switches from quicksort to heapsort for the (sub)partition for which has exceeded the expected recursion depth, so it is guaranteed to run in worst case O(nlogn) for all inputs.
edit: which means it does not need a do nothing first pass and takes mitigating actions only in the worst case.