timsort是通用的还是特定于Python的？

Question

  

Timsort是一个适应性强，稳定的，   自然合并。它有超自然现象   多种部分表现   有序数组（小于lg（N！）   所需的比较，以及少数   N-1），但速度与之前的Python一样快   高度调整的样品杂交   随机数组。

您是否见过在CPython之外使用的 timsort ？它有意义吗？

Answer 1

是的，在CPython之外，特定的或一般的Python中使用timsort是非常有意义的。

目前正在正在努力取代Java的“修改版”合并排序“有了timsort，最初的结果是非常积极的。

Answer 2

该算法非常通用，但其优点是特定于Python。与大多数排序例程不同，Python的list.sort（使用timsort的是什么）关心的是避免不必要的比较，因为通常比较比交换项更昂贵 lot （它总是只是一组指针复制）甚至分配一些额外的内存（因为它总是只是一个指针数组，与任何Python操作中的平均开销相比，开销很小。）

如果你受到类似的限制，那么它可能是合适的。我还没有看到任何其他比较真的那么昂贵的情况： - ）

Answer 3

它看起来并不特别熟悉，但“聪明”。 mergesorts在广泛的软件世界中非常普遍。

至于它是否有意义，这取决于你的排序，以及比较与内存分配的相对成本。在内存受限的环境中，需要最多2 * N字节额外内存的排序不会是一个不错的选择。

Answer 4

现在回答维基百科：将在Java 7中使用timsort从Android复制它。

Answer 5

Timsort现在也在Android中： http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort

Answer 6

您链接的说明看起来很完整。