3 ms·
My memory's actually hazy over whether it was qsort or sort; my intuition is that it would've been qsort because QuickSort is what you'd use when you need an in
by nostrademons 11y ago
My memory's actually hazy over whether it was qsort or sort; my intuition is that it would've been qsort because QuickSort is what you'd use when you need an in-place sort with little additional RAM required, but it's been so long that I honestly don't remember.
- JoachimSchipper 11y agoNot a C++ programmer, but isn't std::stable_sort usually mergesort, while std::sort is usually an introspective quicksort?
- jibalt 11y agoYes.
- nostrademons 11y agoAh, good. I'd initially written std::sort in the comment and then went back and edited it because I was like "Isn't std::sort usually mergesort? That wouldn't work here because it takes extra space." It's been a while since I've written C++.
- chengiz 11y agoYou are assuming qsort is Quicksort and std::sort is not. Both typically use quicksort; but neither is required to.
- StephanTLavavej 11y agoIn C++11, std::sort() is forbidden from being just a quicksort, as it's required to have worst-case O(N log N) complexity.