Merge Sort

[FC Jamison]

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?

[~s.o.s~]

Something like this ?

[FC Jamison]

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!

[~s.o.s~]

Thanks for the nudge in the right direction!

You are welcome..... ;)

[Lylla]

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