While going through Wikipedia's list of sorting algorithms I noticed that there's no stable comparison sort that has O(n*log(n))
(worst-case) time-complexity and O(1)
(worst-case) space-complexity. This surely looks like a theoretical boundary, but I couldn't find more information about it.
How would one proof this?
Note: I know about the lower limit of O(n*log(n))
worst-case time-complexity for comparison sorts.
Despite what that article says, in-place stable Merge Sort can be made O(n log n)
.
Here is a paper that explains two ways to implement it.