Python sorted() 函数 space 复杂度
Python sorted() function space comlexity
我知道 sort() 是 O(1) space 因为排序已经到位。但是，sorted() 函数 returns 一个包含已排序元素的新列表。由于 sorted() returns 是一个包含已排序元素的新数组，这是否意味着使用 sorted() 函数的算法需要 O(n) space 来执行？
sorted() 是否与创建数组并复制所有元素，然后在新数组上 运行 sort() 一样？
for i in sorted(some_list):
// do something
sorted() 使用 Timsort：https://en.wikipedia.org/wiki/Timsort，复杂度为 O(n) space。
我知道 sort() 是 O(1) space 因为排序已经到位。但是，sorted() 函数 returns 一个包含已排序元素的新列表。由于 sorted() returns 是一个包含已排序元素的新数组，这是否意味着使用 sorted() 函数的算法需要 O(n) space 来执行？ sorted() 是否与创建数组并复制所有元素，然后在新数组上 运行 sort() 一样？
for i in sorted(some_list):
// do something
sorted() 使用 Timsort：https://en.wikipedia.org/wiki/Timsort，复杂度为 O(n) space。