Writing a Faster Sorting Algorithm
probablydance.com
Writing a Faster Sorting Algorithm
1–10 of 35 posts
Re: Writing a Faster Sorting Algorithm
#2It 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).
Re: Writing a Faster Sorting Algorithm
#3It 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.
Re: Writing a Faster Sorting Algorithm
#4Every sort algorithm should take locality of data-access into account. Without this, a comparison to other algorithms may not be fair.
Re: Writing a Faster Sorting Algorithm
#5It 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?
Re: Writing a Faster Sorting Algorithm
#6It 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?
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.
Re: Writing a Faster Sorting Algorithm
#7It 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?
AFAIK the STL is free to use any algorithm they want as long as it's O(n log n).
Re: Writing a Faster Sorting Algorithm
#8Earlier quoted context omitted.
Why doesn't the STL switch to the hybrid sorting approach?
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?
Re: Writing a Faster Sorting Algorithm
#9Neat algorithm, but it is largely comparing apples to oranges. std::sort is universal, ska_sort is not:
> Another problem is that I’m not sure what to do for data that I can’t sort. For example this algorithm can not sort a vector of std::sets
> Another problem is that right now there can only be one sorting behavior per type. You have to provide me with a sort key, and if you provide me with an integer, I will sort your data in increasing order. If you wanted it in decreasing order, there is currently no easy interface to do that.
Useful algorithm, but we already knew there are faster algorithms if we introduce additional requirements!
Re: Writing a Faster Sorting Algorithm
#10Earlier quoted context omitted.
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.