Quadratic time to sort in a simple case?

[Dmitry Olshansky]

20-Apr-2013 02:12, Ivan Kazmenko пишет:
>>> 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.
>>
>> Optimization flags if any?
>
> Both "-O" and no-flags give quadratic behavior.
>

I sought after
-O -inline -release

In non-release mode it tests that it's sorted on exit etc.
Anyway it's 8x times as fast with -release -inline for me but the 
progression is similarly bad.

> Well, if that does not convince you the time grows faster than n-log-n,
> maybe this comparison shall (dmd -O, Core i7-2600K @3400 MHz):
>
> n       T, seconds
>   15_000   0.312
>   30_000   1.076
>   60_000   3.775
> 120_000  11.247
>
> With n growing x2, the time grows x3 to x4 at each step.



-- 
Dmitry Olshansky