What Is The Space Complexity Of The Python Sort?
Solution 1:
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)
Solution 2:
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)
Post a Comment for "What Is The Space Complexity Of The Python Sort?"