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

11–20 of 35 posts

Re: Writing a Faster Sorting Algorithm

#11

Post by dom0 »

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?

Re: Writing a Faster Sorting Algorithm

#13

Post by niftich »

adrianN wrote: post #7
imaginenore wrote: post #5

Earlier quoted context omitted.

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

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

Re: Writing a Faster Sorting Algorithm

#15

Post by FlorianRappl »

iherbig wrote: post #12
dom0 wrote: post #11

Earlier quoted context omitted.

"the" STL?

STL means "standard template library." It's perfectly reasonable to say "the standard template 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.

Re: Writing a Faster Sorting Algorithm

#16

Post by raverbashing »

d33 wrote: post #3
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).

I had a feeling that O(N) is pretty impossible for the general use case.

I think there's a (provable) mathematical impossibility to have a general O(N) sorting algorithm

Basically, how many elements do you have to move in a list of N elements to end up with one of the possible orderings

Re: Writing a Faster Sorting Algorithm

#18

Post by beagle3 »

d33 wrote: post #3
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).

I had a feeling that O(N) is pretty impossible for the general use case.

It is impossible for comparison-based sorts; sketch of proof: there are N! different arrangements. sorting is equivalent to figuring which one of those N! arrangements we are seeing. In the worst case, each binary comparison can reduce at most, 50% of the search space. Hence the worst case may need log_2(N!) comparisons, which is O(N log N)

However, it might be possible if comparisons are not essential - e.g. radix sort is (with some assumptions) O(N)

Re: Writing a Faster Sorting Algorithm

#19

Post by maweki »

raverbashing wrote: post #16
d33 wrote: post #3

Earlier quoted context omitted.

I had a feeling that O(N) is pretty impossible for the general use case.

I think there's a (provable) mathematical impossibility to have a general O(N) sorting algorithm Basically, how many elements do you have to move in a list of N elements to end up with one of the possible orderings

You only ever have to move every element once to get a (pre-known) permutation that represents the sorted list.

The problem is the information in a permutation (n! possible orderings) and one can only ever "throw away" half of them on every comparison, leading to log_2(n!) or nlog(n).

Re: Writing a Faster Sorting Algorithm

#20

Post by Xorlev »

raverbashing wrote: post #16
d33 wrote: post #3

Earlier quoted context omitted.

I had a feeling that O(N) is pretty impossible for the general use case.

I think there's a (provable) mathematical impossibility to have a general O(N) sorting algorithm Basically, how many elements do you have to move in a list of N elements to end up with one of the possible orderings

It's not impossible to have a O(N) sorting algorithm if you add more constraints, e.g. use operations other than comparisons.

Most people would be fine with a hybrid radix sort for day to day use.

Post reply on HN