0% completed
Given that MDN says that the sort method on the Array prototype is in place, wou...
Edu
Mar 21, 2022
Given that MDN says that the sort method on the Array prototype is in place, wouldn't the space complexity be O(1)? If that's not correct, could you explain why the space complexity is O(N), please?
0
0
Comments
Design Gurus4 years ago
This is different for different languages and compilers/versions.
Java collection used TimSort which has a space complexity of O(N): https://en.wikipedia.org/wiki/Timsort
It keeps changing with newer versions.
Design Gurus4 years ago
Here is some useful discussion: https://stackoverflow.com/questions/32334319/why-does-collections-sort-use-mergesort-but-arrays-sort-does-not
Edu 4 years ago
Thank you for the answer! So I take from this that, when giving an answer, either you really need to know how sorting affects space complexity in your specific programming language or you should just say it depends and give a range.
Design Gurus4 years ago
Yes. It is always better to know what sorting scheme is used in your programming language.
On this page
Problem Statement
Solution
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity