On Tuesday, 13 March 2012 at 16:11:05 UTC, Andrei Alexandrescu
wrote:
On 3/13/12 10:54 AM, Sean Kelly wrote:
How does the built-in sort do? I ask because the sort routine
I
wrote works the same way, which is optimized for ranges with a
lot of
common elements.
It's not about common (equal) elements, it's about elements for
which comparisons do a lot of work because they have common
prefixes. Consider:
auto arr = [ "aaa", "aab", "aac", "aad" ];
sort!((a, b) => a > b)(arr);
There will be a lot of redundant prefix comparisons because the
sorting method doesn't have information about the common
prefixes.
Trie-based sorting is a more efficient method for ranges of
ranges, see e.g. http://en.wikipedia.org/wiki/Burstsort.
Andrei
Rather than a sort function, I think we'd benefit more from Trie
in std.container. If implemented correctly, it could be self
sorting like RedBlackTree.
