Re:Pattern-defeating quicksort
by partycoder on Friday June 30, 2017 @02:52PM
(#14672902)
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:
https://sites.google.com/site/algoxy/home/elementary-algorit...
...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
In place merge sort exists. It's hard to write tho