python排序的空间复杂性是多少？

Question

python排序采用什么空间复杂度？我无法在任何地方找到任何明确的文件

Answer 1

Python 的内置排序方法是称为 Timsort 的合并排序的衍生，更多信息请点击此处 - https://en.wikipedia.org/wiki/Timsort。

它本质上并不比归并排序更好或更差，这意味着它的平均运行时间O(n log n)和空间复杂度是?(n)

Answer 2

空间复杂度定义为算法在N元素方面需要多少额外空间。即使根据docs，该sort方法也会对列表进行适当排序，但确实会使用一些额外的空间，如实现说明中所述：

timsort可能需要一个包含多达N // 2个指针的临时数组，这意味着32位盒子上的额外字节多达2 * N。排序随机数据时，可能需要一个如此大的临时数组。在具有重要结构的数据上，它可能不需要使用任何额外的堆内存就可以摆脱。

因此，最坏的情况是空间复杂度是O(N)最好的情况O(1)