Thursday, April 30, 2009

MergeSort with minimum allocations

The most recent assignment in my data structures class was writing a sort comparison, including a MergeSort. I realize that MergeSort can't be in-place, but I wondered if there was a way to keep the memory allocations to a minimum. I came up with this, which uses one extra buffer (the same size as the source array). After each pass, the source buffer becomes the target and vice versa. Timings indicate that (for arrays containing random numbers), this beats a quicksort. (Apologies for reformatting introduced by HTML...)
int *IterativeMergeSorter::Sort() {
int* src = mArray;
int* tgt = new int[mLength];
for (int swapSize = 1; swapSize < mLength; swapSize *= 2) {
for (int j = 0; j < mLength; j += (2 * swapSize)) {
int start = j;
int sizeOfSrc1 = min(swapSize, mLength - start);
int src2Index = start + swapSize;
int remainder = max(0, mLength - src2Index);
int sizeofSrc2 = min(swapSize, remainder);
Merge(&tgt[start], &src[start], sizeOfSrc1,
&src[src2Index], sizeofSrc2);
}
int* temp = src;
src = tgt;
tgt = temp;
}
if (src != mArray) {
memcpy(mArray, src, mLength * sizeof(int));
tgt = src;
}
delete[] tgt;
return mArray;
}

2 comments:

Unknown said...

MergeSort can be implemented in-place: http://en.wikipedia.org/wiki/Merge_sort although the implementation is often complicated and (depending on your underlying data structures) can have a negative impact on performance.

Could explain why an in-place mergesort doesn't fit what you're trying to do?

Unknown said...

Ade: I just wanted to reduce memory allocations without implementing (as the wikipedia entry says) a "complicated" chunk of code. also, my code works with an array, which requires fewer memory allocations than a linked list. At some point in the future I may look at the "in-place" algorithm to see what it's like, but for now I'm on to the next assignment for my class. Thanks for the comment.