Re:WikiSort – Fast, stable, O(1) space merge sort algorithm
by jsonified on Saturday March 15, 2014 @07:51AM
(#7404341)
nice to see even in sort() we have innovation!
[ Parent
| on HN ]
Re:WikiSort – Fast, stable, O(1) space merge sort algorithm
by chrismonsanto on Saturday March 15, 2014 @08:41AM
(#7404455)
If you're interested in alternative sort algorithms, you might enjoy the self-improving sort [1]. A simplified tl;dr: given inputs drawn from a particular distribution + a training phase, the result is a sort that is optimal for that particular distribution. The complexity is in terms of the entropy of the distribution, and can beat the typical worst case O(n log n) for comparison sorts.
[1]: http://www.cs.princeton.edu/~chazelle/pubs/selfimprove.pdf