Timsort开发

Question

是否存在针对python的排序实现的此bug的漏洞？

http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/

Answer 1

该版本还包含错误，并打算用于具有最多2^64个元素的数组。然而，在当前的机器上，不可能在Python版本中触发一个超出范围的错误:它为runLen分配了85个元素，这足够(根据全文的分析)用于小于2^49元素的数组。相比之下，当前最强大的超级计算机http://en.wikipedia.org/wiki/Tianhe-2的内存总数约为2^50字节。

目前不可能触发CPython中的错误，因为它需要一个不适合当今机器的数据集。由于无法触发错误，因此无法利用in。

正如本文所提到的，该算法的一些Java实现使用较小的数组，这些数组可以溢出较小的数据集(如果我正确阅读，示例代码中有几百MB )。因为这是缓冲区溢出，所以很有可能会被利用。