python - 如何在 Python 中计算 timsort 的最小运行长度

Question

我对 Python 相当陌生，正在尝试编写一个 timsort 重新实现。在编写程序时，我无法弄清楚如何获得最小运行长度。我咨询过的消息来源将 minrun 描述为：

minrun = N/minrun<=2^N 其中 n 是数组的大小。

我明白我想要做什么，我只是不知道如何在 Python 中做到这一点？

任何想法或示例代码都会非常有用，谢谢！

Answer 1

在 wikipedia trimsort-article中描述了python timsort的内置实现：

minrun 是从 32 到 64 的范围内选择的，因此数据大小除以 minrun 后，等于或略小于 2 的幂。最终算法采用数组大小​​的六个最高有效位，如果设置了任何剩余位，则添加一个，并将该结果用作 minrun。该算法适用于所有数组，包括小于 64 的数组；对于大小为 63 或更小的数组，这将 minrun 设置为等于数组大小，并且 Timsort 减少为插入排序。

你可以这样做：

minrun = length
remaining_bits = length.bit_length() - 6

if remaining_bits > 0:
    minrun = length >> remaining_bits
    mask = (1 << remaining_bits) - 1
    if (length & mask) > 0: minrun += 1

应该是这样，对于任何其他 timsort 问题，请务必查看python timsort。