Writing a Faster Sorting Algorithm

Re:Writing a Faster Sorting Algorithm by adrianN on Tuesday January 03, 2017 @08:03AM (#13308798)

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

[ Parent | on HN ]

Re:Writing a Faster Sorting Algorithm by niftich on Tuesday January 03, 2017 @09:14AM (#13309228)

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

[ Parent | on HN ]

Re:Writing a Faster Sorting Algorithm by sqeaky on Tuesday January 03, 2017 @12:22PM (#13310813)

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

[ Parent | on HN ]

Re:Writing a Faster Sorting Algorithm by wnesensohn on Tuesday January 03, 2017 @12:36PM (#13310949)

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

[ Parent | on HN ]

Re:Writing a Faster Sorting Algorithm by dietbacon on Tuesday January 03, 2017 @03:21PM (#13312681)

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.

[ Parent | on HN ]