Regarding implementing a stable sort for Phobos

[bearophile]

Andrei Alexandrescu:

> 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.

As a benchmark for this new sorting algorithm I suggest to use a poor's man BWT (http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform ). The purpose here is not to create the most efficient BWT.

Bye,
bearophile