3 ms·
nice to see even in sort() we have innovation!
by jsonified 13y ago
nice to see even in sort() we have innovation!
- chrismonsanto 13y agoIf 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 http://www.cs.princeton.edu/~chazelle/pubs/selfimprove.pdf