Re:Bjarne Stroustrup Answers C++ Questions
by jonsen on Tuesday October 15, 2019 @09:56AM
(#21258355)
Try this
[ Parent
| on HN ]
Re:Bjarne Stroustrup Answers C++ Questions
by magicalhippo on Tuesday October 15, 2019 @10:16AM
(#21258566)
I should have stayed in bed today...
Still, probably faster to incorporate a monotonic check in a quicksort first pass, than run a bubble-sort pass which probably won't help much anyway?
Re:Bjarne Stroustrup Answers C++ Questions
by gpderetta on Tuesday October 15, 2019 @10:46AM
(#21258960)
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.