Re:Pattern-defeating quicksort
by gnarbarian on Friday June 30, 2017 @12:45AM
(#14668684)
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).
[ Parent
| on HN ]
Re:Pattern-defeating quicksort
by partycoder on Friday June 30, 2017 @12:47AM
(#14668687)
Just that it takes extra space and that's sometimes a constraint.
https://stackoverflow.com/questions/2571049/how-to-sort-in-p...
In place merge sort exists. It's hard to write tho
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