Hacker News Reader

Comment by imaginenore | Hacker News Reader

Why doesn't the STL switch to the hybrid sorting approach?

The STL sort uses operator<, so they can't implement it as radix sort without changing the interface. Maybe they could manage to special case it for some fundamental types, but most likely they'd need to add a new function, like for stable_sort.

AFAIK the STL is free to use any algorithm they want as long as it's O(n log n).

This is correct. The C++ standard specifies that sort must have a big-O complexity of n log(n). This can be seen on pdf page 925 of this working draft from 2014 [1].

[1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n429...

So providing a faster sort would be a violation?

The standard doesn't seem to say "or better" here, but I know that in other places it does (or least used to say something similar).

No, f = O(n log n) means that f doesn't grow significantly faster than n log n. That is true for f = n log n, but it's also true for f = n. The "or better" is implicit by using big-O.

Note that this wouldn't be true if the standard said that it has to be Θ(n log n).

Big O complexity is an upper bound.

If something is O(1) it's also O(n) and O(n!), since it's an upper bound.

STL does use hybrid sorting. It is usually implemented as an introsort, which begins with a quicksort and switches to heapsort based on the number of elements to be sorted.

Sorry if that wasn't clear. I'm asking why don't they switch to the hybrid sort similar to Boost's, since it's known to be faster for most cases?

They probably should. After all Boost is often a staging area for C++ standard library.

"the" STL?

STL means "standard template library." It's perfectly reasonable to say "the standard template library."

There are several compatible and competing implementations of the C++ standard library.

I think the author just wanted to point out that "the" STL is not valid / accurate here; while the interface and behavior is defined, the implementation is afaik still vendor specific, e.g., the implementation in GCC may be different from the one provided by Microsoft.

Reply on news.ycombinator.com