[gnarbarian]

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

[badminton1]

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

[chii]

https://stackoverflow.com/questions/2571049/how-to-sort-in-p...

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

[badminton1]

Which decreases the space complexity but increases the time complexity.

[_hrfd]

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:

https://sites.google.com/site/algoxy/home/elementary-algorit...

[EvgeniyZh]

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

[tomlx]

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