27

What space complexity does the python sort take? I can't find any definitive documentation on this anywhere

Kamal
  • 560
  • 1
  • 5
  • 14

2 Answers2

28

Space complexity is defined as how much additional space the algorithm needs in terms of the N elements. And even though according to the docs, the sort method sorts a list in place, it does use some additional space, as stated in the description of the implementation:

timsort can require a temp array containing as many as N//2 pointers, which means as many as 2*N extra bytes on 32-bit boxes. It can be expected to require a temp array this large when sorting random data; on data with significant structure, it may get away without using any extra heap memory.

Therefore the worst case space complexity is O(N) and best case O(1)

damores
  • 2,251
  • 2
  • 18
  • 31
  • Well, you sure are sorting something that takes space in memory. – Olivier Melançon Feb 13 '18 at 04:13
  • 6
    Yeah you certainly are, but space complexity is measured in additional memory needed so not the array itself. Nevertheless, I took a look at the implementation description and turns our they do use some more additional space for implementing the algorithm. My answer is updated accordingly – damores Feb 13 '18 at 04:38
19

Python's built in sort method is a spin off of merge sort called Timsort, more information here - https://en.wikipedia.org/wiki/Timsort.

It's essentially no better or worse than merge sort, which means that its run time on average is O(n log n) and its space complexity is Ω(n)

Ry-
  • 218,210
  • 55
  • 464
  • 476
23k
  • 1,596
  • 3
  • 23
  • 52