Bug in timsort!?

[Steven D'Aprano]

Sturla Molden 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.

TimSort is an algorithm, and it is not broken. The algorithm is correct.

Any specific implementation of that algorithm may or may not be correct. As
Zachary has pointed out, the implementation used in CPython has already
been fixed, for versions 2.7.10, 3.4.4, and 3.5.0, and is now correct (as
far as anyone can tell).

Other implementations -- including Java and Android phones -- are not our
responsibility or concern, except so far as they may effect Jython or other
Python code.



-- 
Steven