Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com