Quadratic time to sort in a simple case?

[Xinok]

On Friday, 19 April 2013 at 21:03:23 UTC, Ivan Kazmenko wrote:
> Hi!
>
> Consider a sorted array.  Append an element that is less than 
> all the previous elements.  Then sort the array again by the 
> sort function from std.algorithm.
>
> ....
>
> With n = 30_000 as in the example, this takes time of the order 
> of a second on a modern computer, which is clearly O(n^2).  I 
> am using DMD 2.062.

I filed a bug report for this issue a year ago:
http://d.puremagic.com/issues/show_bug.cgi?id=7767

I've been meaning to fix this issue myself. Time allowing, I'll 
do it soon.