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