Here's the updated code:
Code:
typedef vector< ... > VECTOR;
void merge_sort(VECTOR &vsrc)
{
size_t i, width;
VECTOR vdst(vsrc.size()); // second vector used for merge algorithm
for(width = 1; width < vsrc.size(); width *= 2){ // merge pass
for(i = 0; i < vsrc.size(); i += 2 * width){ // merge sublists
merge_pair(vdst, vsrc, i, min(i+width, vsrc.size()), min(i+2*width, vsrc.size()));
}
vsrc.swap(vdst); // swap ptrs for merged data back to vsrc
}
}
void merge_pair(VECTOR &vdst, VECTOR &vsrc, size_t ileft, size_t iright, size_t iend)
{
size_t il = ileft;
size_t ir = iright;
// merge a pair of sublists
for (size_t idst = ileft; idst < iend; idst++){
if (il < iright && (ir >= iend || vsrc[il] <= vsrc[ir]))
vdst[idst] = vsrc[il++];
else
vdst[idst] = vsrc[ir++];
}
}
Note that sort() and stable_sort() in the Standard Template Library reverse the compare parameters so that the compare operator is less than and true means the elements are out of order. This would look like:
Code:
if (ir < iend && (il >= iright || vsrc[ir] < vsrc[il]))
vdst[idst] = vsrc[ir++];
else
vdst[idst] = vsrc[il++];
I didn't do it this way because it seems more logical to not reverse the order of the parameters. I'm not sure why the STL sort compares were implemented that way.