4 ms·

People were still finding bugs in common implementations of timsort as of 3 years ago. It's not unreasonable to stick with a somewhat more conservative choice f

by dgacmu 8y ago

People were still finding bugs in common implementations of timsort as of 3 years ago. It's not unreasonable to stick with a somewhat more conservative choice for a core library function until there's more reason to have confidence in the implementations of timsort.

arayh 8y ago
This comment got me looking into timsort bugs. This was a really interesting read: http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ http://envisage-project.eu/proving-android-java-and-python-s...
IronBacon 8y ago
You know what, I'm not surprised at all. Didn't one of the most simple algorithms, binary search, suffered of a bug in a standard library (was it Java?) a few years ago? If IIRC it was a corner case, I should check it because I don't recall the details, but it looked robust code. Edit: I think it's this one https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
deleted 8y ago
[deleted]
xapata 8y ago
If I recall correctly, the bug only applied for arrays/lists of length greater than 2 to the more-than-astronomical. Not something that anyone ever encountered in the wild, because current hardware doesn't have enough memory. Edit: The article linked in the other comment says the Java dev team didn't even bother to implement the "proper" fix, but merely adjusted how much space is allocated.