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?

Something like this ?

Yeah...like that.

I actually saw that in my research, but didn't think I could convert it to what I needed.

Your suggestion prompted me to look at the code a little closer, and I came up with this solution:

``````template <class T>
void mergeSort(vector<T>& s) {
vector<T>* temp = new vector<T>(s.size());
if(temp != NULL) { mergeHelper(s.begin(), 0, s.size(), temp->begin()); }
delete temp;
}

template <class T>
T max(int x, int y) {
if(x > y) { return x; }
else { return y; }
}

template <class Itr>
void mergeHelper(Itr start, unsigned int low, unsigned int high, Itr temp) {
if (low + 1 == high) return;
else {
unsigned int center = ((high + low) / 2);
int l = low;
int h = center;

mergeHelper(start, low, center, temp);
mergeHelper(start, center, high, temp);

for(int i = 0; i < (high - low); i++) {
if (l < center && (h == high || max(start[l], start[h]) == start[h])) {
temp[i] = start[l];
l++;
}
else {
temp[i] = start[h];
h++;
}
}

for(i = low; i < high; i++) { start[i] = temp[i - low]; }
}
}``````

Thanks for the nudge in the right direction!

Thanks for the nudge in the right direction!

You are welcome..... ;)

Thank you very much for your post! It is very useful!

commented: Use comment feature for thanks next time! -3
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.