时间排序是通用的还是Python特有的？

Question

Timsort是一种适应性的、稳定的、自然的合并方式。它在多种偏序阵列(小于lg(N!) )上具有超自然的性能。虽然需要进行比较，但与Python之前在随机数组上进行的高调优样本混合算法一样快。

你见过时间排序在CPython之外使用过吗？说得通吗？

Answer 1

是的，在CPython之外使用timsort (具体地说，或者一般地说是Python )是有意义的。

目前有一个正在进行的努力可以用timsort代替Java的“修改后的合并排序”，最初的结果是非常积极的。

Answer 2

该算法非常通用，但好处是Python特有的。与大多数排序例程不同，Python的list.sort (也就是使用timsort的方法)所关心的是避免不必要的比较，因为通常比较比交换项(通常只是一组指针副本)或甚至分配一些额外的内存(因为它总是一个指针数组，与任何Python操作中的平均开销相比，开销都要小得多)。

如果您受到类似的限制，那么它可能是合适的。不过，我还没有看到任何其他情况下，比较真的那么昂贵，尽管:-)

Answer 3

这看起来不是特别熟悉，但“智能”合并是相当普遍的在广泛的软件世界。

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