News for hackers. Stuff that matters.
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

There are no comments on this comment yet.