3 ms·
Why does the BSD implementation compare with copies of the data outside the original array? Is there a performance benefit to doing this?
by rhaps0dy 10y ago
Why does the BSD implementation compare with copies of the data outside the original array? Is there a performance benefit to doing this?
- MaxLeiter 10y agoEDIT: I skimmed the article and my previous answer was completely wrong. The BSD implementation is quicksort, which doesn't have a duplicate (AKA auxiliary) array. Their implementation of mergesort has an auxiliary/duplicate array for the actual merging - that's common. In-place mergesorts exist, but the effort isn't usually worth it. You can, however, eliminate the need for copying to the duplicate array (which they may do) by invoking sort twice - once takes input from the actual array and puts the sorted output in the duplicate, and the second takes from the duplicate and puts it back into the default. Somehow, you can merge the two together to speed up the algorithm (I personally don't know how, however they can be found implemented here: http://algs4.cs.princeton.edu/22mergesort/MergeX.java.html http://algs4.cs.princeton.edu/22mergesort/MergeX.java.html)