-1

I know that sort() is O(1) space since the sorting is in place. However, sorted() function returns a new list with sorted elements. Since sorted() returns a new array with sorted elements, does this mean that an algorithm that uses the sorted() function takes O(n) space to execute? Would sorted() be the same thing as creating an array and copying all elements, then running sort() on that new array?

for i in sorted(some_list):
    // do something
David
  • 5
  • 4
  • O(n) space? Yes. Same as copy + sort()? I think so. For more information, see https://stackoverflow.com/questions/10948920/what-algorithm-does-pythons-sorted-use. – mackorone Feb 15 '21 at 21:27
  • Your assumption that `sort()` is O(1) space complexity is wrong (only the best case is, but O is always communicating the worst case). See the dupe. – DeepSpace Feb 15 '21 at 21:28

1 Answers1

0

sorted() uses Timsort: https://en.wikipedia.org/wiki/Timsort, which has O(n) space complexity.

Chance
  • 440
  • 2
  • 6