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?

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!

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

Comments
Use comment feature for thanks next time!
This question has already been answered. Start a new discussion instead.