以Python表示的Timsort执行时间

Question

我正在研究一些排序算法和它们的执行时间。我用Python实现了一些算法，我正在测量它们对一些数组进行排序所需的时间。我发现Python在本地实现了Timsort作为列表的排序算法。但是，我想将原生Timsort与我在GitHub (this one)上找到的实现进行比较。为什么本机实现需要0.000630140304565秒来对包含51200个元素的数组进行排序，而我之前链接的实现需要40.7546050549秒来对相同的数组进行排序？

编辑以获取时间我在执行排序算法之前和之后使用了"time.time()“，然后我只是做了一些改变。

我期望本机实现会更快，但并不是那么快。事实上，我还在Python中实现了其他排序算法，例如，Merge-Sort对同一数组进行排序需要0.148133039474秒。我没想到Merge-Sort和Timsort的Python实现之间会有这么大的区别。

所以问题是我发现的实现效率不高，也不是真正的EDIT2。对不起，伙计们，我刚刚发现Timsort是theta(nlgn)，我相信这是正确的实现。现在的问题是:是否存在有效的Timsort的Python实现？

Answer 1

2020年11月24日

下面是2018年10月(在这里提出原始问题之前)非常完整且经过测试的timsort的python实现：

https://gist.github.com/ruminations/89a045dc0ef7edfb92304a0de0752ee0

评论包括用于教育目的的有用链接。