Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Writing a Faster Sorting Algorithm

probablydance.com

Post reply on HN
Print view View original

31–35 of 35 posts

Re: Writing a Faster Sorting Algorithm

#31

Post by tveita »

imaginenore wrote: post #5
testerofwaters wrote: post #2

It might just be faster because the author is comparing their hybrid radix sort implementation to std::sort (which is comparison-based). Would be more valid to compare to Boost's "spreadsort" which is similarly a hybrid radix sort algorithm (and also outperforms std::sort).

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.

Re: Writing a Faster Sorting Algorithm

#32

Post by wnesensohn »

sqeaky wrote: post #30
niftich wrote: post #13

Earlier quoted context omitted.

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

Re: Writing a Faster Sorting Algorithm

#33

Post by Animats »

This is a classic. In fact it's close to the first algorithm ever patented - SyncSort, patented in 1971. Still being developed and sold, SyncSort remains the leading technology for big sorts.[1] When you need to sort a few terabytes, they have a product for that. It's a radix sort with self-adjusting bucket boundaries. So it can deal with keys that are not well distributed.

[1] http://www.syncsort.com/en/Products/Sort

Re: Writing a Faster Sorting Algorithm

#34

Post by dietbacon »

sqeaky wrote: post #30
niftich wrote: post #13

Earlier quoted context omitted.

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

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.

Post reply on HN