Regarding implementing a stable sort for Phobos

[Andrei Alexandrescu]

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