Regarding implementing a stable sort for Phobos

[Xinok]

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.