I am trying to learn how to write a merge sort function, but I have only gotten so far with the book I am using now:
template <class T>
void mergeSort(vector<T>& s) { mergeHelper(s.begin(), 0, s.size()); }
template <class Itr>
void mergeHelper(Itr start, unsigned int low, unsigned int high) {
// If current element is the only element in the vector, return the element
if (low + 1 == high) return;
// Find the center of the current vector
unsigned int center = ((high + low) / 2);
// Sort lower half
mergeHelper(start, low, center);
// Sort upper half
mergeHelper(start, center, high);
// Combine consecutive sorted ranges [first, middle) and [middle, last)
// into a single sorted range [first, last)
inplace_merge(start + low, start + center, start + high);
}
I understand "what" the inplace merge function is supposed to do...but I'll be damned if I can figure out how to write the code for it and I have been unsuccessful in my online searches.
How would I write the code for my own inplace_merge function?