Android/Java/Python平台的 Timsort 排序算法有 Bug[讨论] 2 月前• aoi 分享 •排序算法 , 算法
Timsort 是一个混合排序算法，综合了合并排序（Merge Sort）和插入排序（Insertion Sort）。 Tim Peters 于 2002 年为 Python 语言开发实现。Joshua Bloch 后来把这个混合排序算法移植到了 Java 语言（在 java.util.Collections.sort 和 java.util.Arrays.sort 中）。Joshua 设计了 Java 集合，他也曾经指出大多数二分查找算法有问题。目前，Android SDK、Sun JDK 和 OpenJDK 的默认排序算法均为 Timsort。鉴于这些平台都大受欢迎，大量计算机、云服务和手机都在使用 Timsort 算法。
Envisage 团队之前开发了一个名为 KeY 验证工具，成功验证了 Java 实现的计数和基数排序。在此之后，他们又在寻找新挑战。这次他们瞄上了 Timsort。不幸的是，他们这次没能证明 Timsort 的正确性。在更进一步分析之后，他们找到了该算法的 Bug。（有趣的是，Python实现中这个早已出现过了。）Envisage 在这篇文章展示了他们是如何发现这个Bug，最后也给出了修复方案。
› RSS订阅算法话题，关注算法相关的优秀工具资源和文章！