I believe this is a pretty hard one.
The idea is to use merge sort (toke me a bit of time to prove it’s O(n log n) and quite some time to debug…). Since recursion is also space-expensive, we use while loop to replace recursion.
Here’s the code… pretty long this time. And I think this code is a bit ugly. Don’t know how to beautify it yet.