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
