Here are minimal code examples of merge sort using C++ vectors. The top down example is inefficient since it literally splits and merges lists as opposed to logically doing this using vector iterators, but it makes the example easier to read.
top down
Code:
typedef vector<...> LIST;
LIST merge_sort(LIST &list)
{
// if size == 1, consider list sorted and return it
if(1 >= list.size())
return(list);
// else split list into two and recursively call merge_sort()
// until list size is 1
LIST::iterator middle = list.begin() + (list.size() / 2);
LIST left(list.begin(), middle); // left = 1st half of list
LIST right(middle, list.end()); // right = 2nd half of list
list.clear(); // optional: clear out the no longer needed list
left = merge_sort(left);
right = merge_sort(right);
// merge the two lists returned from previous iterations of merge_sort()
list = merge_pair(left, right);
return(list);
}
LIST merge_pair(LIST &left, LIST &right)
{
size_t il = 0;
size_t ir = 0;
// merge two lists and return a single list
LIST list(left.size() + right.size());
for(size_t iout = 0; iout < list.size(); iout++){
if (il < left.size() && (ir >= right.size() || left[il] <= right[ir]))
list[iout] = left[il++];
else
list[iout] = right[ir++];
}
return(list);
}
bottom up
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++];
}
}