Mark Gritter (markgritter) wrote,
Mark Gritter

The hits keep on coming

Remember when I told you not to not to trust published algorithms, even famous ones bearing proofs? And how even functional programming experts screw up the Sieve of Eratosthenes?

Well, you should also not have been trusting TimSort, which got implemented (with the same bug) as Python's array sort and Java's collection sort: Proving Android, Java, and Python's Sorting Algorithm is Broken and How to Fix It.

I am dismayed that Java's response to the bug was to tune one of the algorithm parameters to a higher value so that it will take infeasibly-large arrays to trigger the bug, but waste some of everybody's memory in the meantime. (This was already the case in Python.)
Tags: algorithm
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.