Bug in timsort!?

[Mark Lawrence]

On 25/02/2015 16:04, Peter Otten wrote:
> Sturla Molden wrote:
>
>> On 24/02/15 22:34, Roy Smith wrote:
>>> http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
>>>
>>
>> This is awful. It is broken for arrays longer than 2**49 elements. With
>> 8 bytes per PyObject* pointer this is >4096 terabytes of RAM. I don't
>> see how we can fix this in time.
>>
>> Oh yes, and they mention that TimSort is used on billions of devices due
>> to Android mobile phones. This is clearly very relevant for mobile
>> phones. Next thing you know your litte Samsung Galaxy with more than
>> 4096 terabytes breaks down from a stack overflow in TimSort.
>
> Yeah, I'm looking forward to see comparable bugs being closed as "cannot
> reproduce" by some of the jokers. I suppose that you all had a note
> scribbled on the margin of your copy of Arithmetica that this cannot happen
> with arrays of lengths seen in practice until 2038 or so.
>
> 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.
>

Reading the bug report http://bugs.python.org/issue23515, specifically 
msg236586, it looks as if the proposed fix was wrong and one of the 
smarter members of the python community fixed it.

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence