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
