On: Ask HN: What's the most elegant piece of code you'...

[StephanTLavavej]

Minor correction: qsort() is CRT, std::sort() is STL.

[nostrademons → StephanTLavavej]

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 → nostrademons]

Not a C++ programmer, but isn't std::stable_sort usually mergesort, while std::sort is usually an introspective quicksort?

[jibalt → JoachimSchipper]

Yes.

[nostrademons → jibalt]

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++.

[chengiz → nostrademons]

You are assuming qsort is Quicksort and std::sort is not. Both typically use quicksort; but neither is required to.

[StephanTLavavej → chengiz]

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.