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.
Ah, 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++.
Comments
Minor correction: qsort() is CRT, std::sort() is STL.
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.
Not a C++ programmer, but isn't std::stable_sort usually mergesort, while std::sort is usually an introspective quicksort?
Yes.
Ah, 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++.
You are assuming qsort is Quicksort and std::sort is not. Both typically use quicksort; but neither is required to.
In C++11, std::sort() is forbidden from being just a quicksort, as it's required to have worst-case O(N log N) complexity.