I have an algorithms library called NDex. I am in the process of upgrading it to a new version. Part of this upgrade involves providing two versions of many algorithms: an in-place version and a version that copies the results to a destination list.

I will be providing two sort variations: quick sort and merge sort. The merge sort is stable.

I am curious whether quick sort is better than, say, heap sort when copying items to a new list.

Merge sort uses a buffer internally. I am curious when doing a merge sort whether I can double up the destination as the buffer.

I was hoping someone could give me some advice or point me to some useful material.

  • Why have two versions when all you need is to provide a copy function, if people want it in-place that call whateverSort(theirArray) and if they want a copy they call whateverSort(copy(theirArray)) ? Is the additional O(n) that particular much addition to the sorts you're doing such that the copying sort would be of significantly better performance? If so just do a copying sort and make it take a source and dest, and for in-place people give it the same source and dest.. – Jimmy Hoffa May 24 '13 at 23:01
  • @JimmyHoffa I had that idea. Unfortunately, it's not always easy to recreate the list on the left-hand side of the expression and creating a local variable ruins the "flow" of the expressions. I am debating whether O(n) is that big of a deal. Looking at other libraries that do copy sorts, they just copy and sort. – Travis Parks May 25 '13 at 1:10
  • Don't go publishing efficient sort library's because it's easy, more than enough sorting library's already exist, publish it regardless of not being easy if you're going to create a new one :P – Jimmy Hoffa May 25 '13 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.