Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

EDIT: 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)



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: