Bug in timsort!?

[Mark Lawrence]

On 25/02/2015 13:58, 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.
>
>
> Sturla
>
>

When I were a lad we only had one bit of data, and we were only able to 
utilise half of that.

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

Mark Lawrence