Search code examples
algorithmsortingcomplexity-theoryproof

Stable comparison sort with O(n * log(n)) time and O(1) space complexity


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.


Solution

  • 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.