Menu
What space complexity does the python sort take? I can't find any definitive documentation on this anywhere
505
What Is Space Complexity? The space complexity of an algorithm describes the amount of memory an algorithm takes to run in terms of the characteristics of the input. In other words, we can say space complexity is the approximate total extra space required by the program to run.
There is no built-in constant-space sort. can you describe more about your constraints? What is the nature / size of your data? Nobody is stopping you from writing your own sorting function.
The space complexity of Selection Sort is O(1). This is because we use only constant extra space such as: 2 variables to enable swapping of elements. One variable to keep track of smallest element in unsorted array.
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)
76
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
