Ad:

C Discussion Thread
Unsolved
Views: 6253

Feb 27th, 2007

Merge Sort

Expand Post »

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:

C Syntax (Toggle Plain Text)
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);
}
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?

Last edited by FC Jamison; Feb 27th, 2007 at 3:23 am.

Similar Threads

hw assignment help on selection & merge sort in C
Merge Sort Code Not Working Properly In Vc++.code Is Given in C++
another merge sort question in C++
Merge sort in C++

FC Jamison

Team Colleague

Reputation Points: 92

Solved Threads: 21

Posting Pro in Training

Offline

436 posts
since Jun 2004

Permalink

Feb 27th, 2007

Re: Merge Sort

Something like this ?

~s.o.s~

Super Moderator

Featured Poster

Reputation Points: 3241

Solved Threads: 719

Failure as a human

Offline

8,873 posts
since Jun 2006

Permalink

Feb 28th, 2007

Re: Merge Sort

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:

C Syntax (Toggle Plain Text)
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]; }
	}
}
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!

FC Jamison

Team Colleague

Reputation Points: 92

Solved Threads: 21

Posting Pro in Training

Offline

436 posts
since Jun 2004

Permalink

Mar 1st, 2007

Re: Merge Sort

Click to Expand / Collapse Quote originally posted by FC Jamison ...

Thanks for the nudge in the right direction!

You are welcome.....

~s.o.s~

Super Moderator

Featured Poster

Reputation Points: 3241

Solved Threads: 719

Failure as a human

Offline

8,873 posts
since Jun 2006

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C Forum Timeline: Problem with memory allocation =(

Next Thread in C Forum Timeline: Find complex no.

DaniWeb Message

Cancel Changes

User Name
Password