Bug in timsort!?

[Peter Otten]

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.