|
|
|
|
|
|
by stjepang
3476 days 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 |
|
|