Bug in timsort!?

[Chris Kaynor]

On Wed, Feb 25, 2015 at 8:44 AM, Sturla Molden <sturla.molden at gmail.com> wrote:
>
> On 25/02/15 17:04, Peter Otten wrote:
>
>> These guys found a bug that is subtler than what most of us have dealt with
>> in a widely used piece of code originally developed by one of the smarter
>> members of the python "community".
>>
>> I bow my head to them and say thank you.
>
>
> I am not joking about that. It is more the hype this gets that indicates TimSort is already broken today, and even on your cell phone.

While the CPython implementation was only broken for arrays of length
larger than 2**49, aka, practically not broken, the Java
implementation (such as used on Android phones) was broken with arrays
of length > 67,108,864 at the time the post was made. While still very
large, an array of 67 million elements is well within the realm of
possibility today. The Java fixes (so far) have only extended the
number out, rather than actually fix the underlying problem - the
CPython fixes that were committed implement the full proven fix, so
CPython should now be able to handle infinite length arrays (once we
can build computers with that much storage...).