Quadratic time to sort in a simple case?

[Dmitry Olshansky]

23-Apr-2013 05:17, Xinok пишет:
> On Saturday, 20 April 2013 at 16:35:25 UTC, Dmitry Olshansky wrote:
>> And this all is good but TimSort allocates O(N) memory. The constant
>> in front of N is smallish less then 1.0 but it could cause some grief.
>
> Worst case is O(n/2), but it starts small and doubles in size as needed.
> On a partially sorted array, it may only use a small amount of memory.

Good to know, still it's something to keep in mind.
Especially for allocation-free minded folks.

-- 
Dmitry Olshansky