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

Question

Timsort是一个适应性,稳定,自然的合并.它在多种部分有序阵列上具有超自然性能(需要少于1g(N!)的比较,并且只有N-1),但速度与Python先前在随机阵列上高度调谐的样本混合一样快.

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

Answer 1

是的,在CPython之外,特定的或者Python中使用timsort是非常有意义的.

目前正在努力用timsort取代Java的"修改合并排序",初步结果非常积极.

Answer 2

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

如果你受到类似的限制,那么它可能是合适的.我还没有看到任何其他情况下比较真的那么贵,但是:-)

Answer 3

它看起来并不特别熟悉,但"智能"合并在广泛的软件世界中非常普遍.

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