What is the space complexity of the python sort?

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

2 Answers

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)

Python's built in sort method is a spin off of merge sort called Timsort, more information here - .

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)