Should Phobos use Timsort instead? (with a small tweak)

[Stewart Gordon]

On 08/11/2011 03:28, Xinok wrote:
<snip>
> Take a look at the graphic here:
> http://cl.ly/3L1o111u1M232q061o2N

404

> That's the extra step that I propose adding to Timsort, if it were
> implemented in Phobos. By doing a single range swap, you can reduce the
> space requirement from O(n/2) to O(n/4). My algorithm utilizes it so
> that only O(n/1024) additional space is required.
<snip>

Uh, O(n/2), O(n/4) and O(n/1024) are all the same thing.

Stewart.