Proving that Android’s, Java’s and Python’s sorting algorithm is broken (2015)

http://www.envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/?utm_content=bufferfe2d8&utm_medium=social&utm_source=facebook.com&utm_campaign=buffer

by CarolineW • 9 years ago

46 8 9 years ago

envisage-project.eu

gleenn• 9 years ago

Pretty remarkable this has been sitting in production on millions of devices and nobody noticed until someone tried to formally verify it. Nobody at Google notice the stacktraces in TimSort code? Almost every mobile app I've written in production phones home when the app crashes. Is it just that unlikely to occur?

realslimjd2• 9 years ago

It was literally impossible for it to occur. The numbers it required were so large that there's no device with enough memory for the bug to show up.

goldfire• 9 years ago

Unless I misunderstand their test code, the article says they could reproduce the problem using an array of 67108864 Integer objects. That doesn't sound like an impossible amount of memory.

mangatmodi• 9 years ago

I read this long time back. I believe that Java rolled out a fix later to make it impossible to reproduce.

realslimjd2• 9 years ago

Not only was it fixed in Java, but Python patched the bug in one day.

https://bugs.python.org/issue23515

btown• 9 years ago

Can mods add a [2015] tag to the title? While this is an impressive analysis, it’s not a cause for panic now as it has long been patched.

Proving that Android’s, Java’s and Python’s sorting algorithm is broken (2015)

Related Stories