3 ms·

The original TimSort had a problem: http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ http://envisage-p

• stjepang 10y ago
  Author here. Yes, this is an interesting problem TimSort used to have. A counterexample to incorrect TimSort is sequence "120, 80, 25, 20, 30". This simple sequence could have been easily discovered by generating sequences randomly and verifying that the TimSort invariants hold on it. The fact that it took 13 years to discover the bug (using formal verification!) is just silly :) Fortunately, the problem is easy to fix and there's a brief mention of it in the comments: https://is.gd/txKd4I https://is.gd/txKd4I
• deleted 10y ago
  [deleted]