Bug in timsort!?

[Roy Smith]

In article <mailman.19183.1424872728.18130.python-list at python.org>,
 Sturla Molden <sturla.molden at gmail.com> 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.

Keep in mind that the phone I cary around today has more memory (and 
probably more CPU) than the biggest supercomputers that existed when I 
was in college.