undefined | Better HN

0 pointsastrada11y ago0 comments

Well, sometimes you have space constraints. The O(n) extra-space required by mergesort isn't always available. But if you don't have space constraints, mergesort is a very good choice because you can easily write a highly scalable parallel version of the algorithm.

0 comments

boomzilla11y ago

You can implement merge sort in place too:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22....

Looks like the algo is more complicated, but surely implementable. In most modern architectures, the key for performance is how one exploits the caching behavior. Quicksort is very cache friendly, as well as the common implementation of merge sort. Not so for heapsort.

phkahler11y ago

"The O(n) extra-space required by mergesort isn't always available."

Heapsort

lsb11y ago

No, but mergesort can easily fall back to dumping its sorted contents to disk, for later merging; this disk-based merge sort was invented by van Neumann in the 1940s, and is how the unix utility sort works (dozen-way merge of sorted shards of a file).

nly11y ago

Mergesort gets pretty damn efficient, even with moderate buffer space.

j / k navigate · click thread line to collapse