Quadratic time to sort in a simple case?

[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.