Bug in timsort!?

[Chris Angelico]

On Thu, Feb 26, 2015 at 2:05 AM, Sturla Molden <sturla.molden at gmail.com> wrote:
> On 25/02/15 15:33, Chris Angelico wrote:
>
>> It's even worse than that. Unless you have a list of 2**49 references
>> to the same few objects, you're going to need to have some actual
>> content for each one. The absolute best you could do is to sort
>> integers, which would take 32 bytes each [1]; if you're sorting
>> strings, they'll be 90 bytes each, so the integers are our best bet.
>> So add another *five* powers of two to the RAM requirements.
>
>
> In that case you also need to add the PyObject_HEAD overhead for each
> object. ;-)

Not sure about that, because the figure of 32 bytes came from
sys.getsizeof(). So assuming there's no significant malloc overhead
(there shouldn't be any alignment padding, for instance), 32 bytes
ought to be it - pack 'em all in.

ChrisA