Hacker News Reader

I like merge sort. Average time may be worse, but it's upper bound is better and it is conceptually cleaner and easier to understand (IMO).

Just that it takes extra space and that's sometimes a constraint.

In place merge sort exists. It's hard to write tho

This is beautiful. I will try to implement this once i'm at home ...

Which decreases the space complexity but increases the time complexity.

No, the time complexity is the same: O(n log n). The author of the top answer links to his book, where you can find a proof of time complexity:

...but it increases run time. It's fine not to care on hidden constants while analyzing algorithms, but not while using them in real life