stack overflow in merge sort of linkedlist

hello everyone,
I have created a template linked list, and im using merge sort to sort it.
the problem is i get stack overflow for input of 5000+ elements, but its working on like 2000 elements.

First i have the merge_sort and the merge routines both recursive, i change the merge into iterative one, but i still get stackover flow.
How can i solve it?
thanks in advance.

the code:

Code:

template <class T>
Node<T>* LinkedList<T>::merge_sort(Node<T>* head)
{

	Node<T>* head_one;
	Node<T>* head_two;
	

	if((head == NULL) || (head->get_next() == NULL)) 
	 return head;

	head_one = head;
	head_two = head->get_next();

	while ((head_two != NULL) && (head_two->get_next() != NULL))
	{
		head = head->get_next();
		head_two = head->get_next()->get_next();
	}
	head_two = head->get_next();
	head->set_next(NULL);
	
	return merge(merge_sort(head_one), merge_sort(head_two));
}


template <class T>
Node<T>* LinkedList<T>::merge(Node<T>* head_one, Node<T>* head_two)
{
	Node<T>* head_three;
	Node<T>* tmp_ptr;

	if(head_one == NULL)
		return head_two;

	if(head_two == NULL)
		return head_one;
	if (*(head_one->get_data()) < *(head_two->get_data()))
	{
		head_three = head_one;
		while(head_one->get_next() != NULL)
		{
			if(*(head_one->get_next()->get_data()) < *(head_two->get_data()))
				head_one = head_one->get_next();
			else
			{
				tmp_ptr = head_two->get_next();
				head_two->set_next(head_one->get_next());
				head_one->set_next(head_two);
				head_two = tmp_ptr;
				head_one = head_one->get_next();
			}
		}
		head_one->set_next(head_two);
	}
	else
	{
		head_three = head_two;
		while(head_two->get_next() != NULL)
		{
			if(*(head_two->get_next()->get_data()) < *(head_one->get_data()))
				head_two = head_two->get_next();
			else
			{
				tmp_ptr = head_one->get_next();
				head_one->set_next(head_two->get_next());
				head_two->set_next(head_one);
				head_one = tmp_ptr;
				head_two = head_two->get_next();
			}
		}
		head_two->set_next(head_one);
	}

	return head_three;
}

After looking at the code for a few minutes I've realised that the problem is that your code for splitting the list up is not dividing the list evenly in two. All but two of the items go in the first list, and it is this huge unevenness that would eventually lead to stack overflow when there are enough items. It also means that your code will have been seriously underperforming.
The bug is on this line:

Code:

		head_two = head->get_next()->get_next();

That doesn't move head_two along by two places from where head_two was.

Note that I haven't verified the correctness of your merge function and it could easily also be broken since it so far has only had to merge cases where the second list has only two items. Generally it would be structured with the while outside the if's rather than an if with two while's in it (hence how you're finding a need to put if's inside the while's as well).

Thank you very much iMalc, it solved my problem, it required some more changes but now the sort is working as it should.
Just for you to know, i posted this problem in 3 other forums and none of them had any idea what to do with it.

it still doesnt work with recursive merge, but only with iterative merge, is there a chance it can work with recursive merge?
the sort is working fine, and the program is running.
the code of merge sort:

Code:

template <class T>
Node<T>* LinkedList<T>::merge_sort(Node<T>* head)
{

	Node<T>* head_one;
	Node<T>* head_two;
	

	if((head == NULL) || (head->get_next() == NULL)) 
	 return head;

	head_one = head;
	head_two = head->get_next();

	while ((head_two != NULL) && (head_two->get_next() != NULL))
	{
		head = head->get_next();
		head_two = head_two->get_next()->get_next();
	}
	head_two = head->get_next();
	head->set_next(NULL);
	
	return merge(merge_sort(head_one), merge_sort(head_two));
}

recursive merge:

Code:

template <class T>
Node<T>* LinkedList<T>::merge(Node<T>* head_one, Node<T>* head_two)
{
	int i=0;

	Node<T>* head_three;
	Node<T>* tmp_ptr;

	if(head_one == NULL)
		return head_two;

	if(head_two == NULL)
		return head_one;

	if (*(head_one->get_data()) < *(head_two->get_data()))
	{
		head_three = head_one;
		head_three->set_next(merge(head_one->get_next() , head_two));
	}
	else
	{
		head_three = head_two;
		head_three->set_next(merge(head_one, head_two->get_next()));
	}
	return head_three;
}

iterative merge:

Code:

template <class T>
Node<T>* LinkedList<T>::merge(Node<T>* head_one, Node<T>* head_two)
{
	int i=0;

	Node<T>* head_three;
	Node<T>* tmp_ptr;

	if(head_one == NULL)
		return head_two;

	if(head_two == NULL)
		return head_one;
	if (*(head_one->get_data()) < *(head_two->get_data()))
	{
		head_three = head_one;
		while(head_one->get_next() != NULL && head_two != NULL)
		{
			if(*(head_one->get_next()->get_data()) < *(head_two->get_data()))
				head_one = head_one->get_next();
			else
			{
				tmp_ptr = head_two->get_next();
				head_two->set_next(head_one->get_next());
				head_one->set_next(head_two);
				head_two = tmp_ptr;
				head_one = head_one->get_next();
			}
		}
		if (head_two != NULL)
			head_one->set_next(head_two);
	}
	else
	{
		head_three = head_two;
		while(head_two->get_next() != NULL && head_one != NULL)
		{
			if(*(head_two->get_next()->get_data()) < *(head_one->get_data()))
				head_two = head_two->get_next();
			else
			{
				tmp_ptr = head_one->get_next();
				head_one->set_next(head_two->get_next());
				head_two->set_next(head_one);
				head_one = tmp_ptr;
				head_two = head_two->get_next();
			}
		}
		if (head_one != NULL)
			head_two->set_next(head_one);
	}

	return head_three;
}

again, thanks!!!!

If you take a quick look at my website (link in signature), you might see why I knew enough to help.
Incidentally, posting on many forums is often frowned upon because some people might go to the effort of solving your problem only to find that it has already been answered elsewhere. Make sure you update those other sites to say what has been solved.

I couldn't see anything wrong with you recursive merge so I threw it into my own sorting program which contains a basic testbed and initially it just failed the stability test, but after reversing the comparison and swapping the if and else clauses it passed all tests. Note that the stability test isn't important, as it will sort just fine either way. I also removed the two unused variables.
What symptoms are you seeing when using the recursive merge? Do you get a stack overflow again, or does it crash, or not sort correctly, or does the list lose some nodes or...?


My existing code currently all assumes an intrusive list, so it isn't as usefully templated as yours. After the modifications I made for it to plug straight into my program, the exact code I used was this:

Code:

template <class TItem>
TItem* RecursiveMerge(TItem* head_one, TItem* head_two)
{
	TItem* head_three;

	if (head_one == NULL)
		return head_two;

	if (head_two == NULL)
		return head_one;

	if (*head_two < *head_one)
	{
		head_three = head_two;
		head_three->next = RecursiveMerge(head_one, head_two->next);
	}
	else
	{
		head_three = head_one;
		head_three->next = RecursiveMerge(head_one->next, head_two);
	}
	return head_three;
}

There's no change of any significance here, indicating that the code was correct to begin with.

Hi again iMalc,
I get stack overlflow for 10000 elements, but for 5000 the sort is working, i dont mind about stability.
The unused variables were just for testing few things, i forgot removing them before posting but removed them later.

Well it sounds like your stack size just wont really support huge amounts of recursion. Removing the unused variables might help the debug build work at greater numbers. Also, you can remove head_three:

Code:

template <class TItem>
TItem* RecursiveMerge(TItem* head_one, TItem* head_two)
{
	if (head_one == NULL)
		return head_two;

	if (head_two == NULL)
		return head_one;

	if (*head_two < *head_one)
	{
		head_two->next = RecursiveMerge(head_one, head_two->next);
		return head_two;
	}
	else
	{
		head_one->next = RecursiveMerge(head_one->next, head_two);
		return head_one;
	}
}

But yeah even that will only get you so far with the stack size you have.

The iterative version you have is clearly built around turning the recursive version into an iterative one. However it would be much shorter and simpler if it were based around a while loop that goes: "while both lists are not empty... " and then after that, concat what's left of one list onto the merged part.

O_o

Assuming "x86" styled hardware on a modern operating system, you should really be able to sort more than 10,000 elements even if you have one call on the stack for every element, and you really should not have one call on the stack for every element.

I'd suggest you wrap a native type, such as `int', with a class and then user a debugger to see if the merging operation isn't being called more than it should be off one side.

If you want to post a complete header, one that I can compile with fiddling around, I'll try it here and see what happens.

Soma

Yes one piece of information we haven't gotten from you is what compile is this, and can you find out what the stack size is set to. I've been suspecting for some time that it is set to less than the usual default of 1MB.

im using visual studio 2008, (dont remeber if its x64, it doesnt say in "about").
it was an exercise in c++ course, and i needed to appeal over the grade.
The problem is i lose points for each change i make in the code so eventually i had to submit the work with the recursive merge because the iterative version changes the entire method.
the exercise was about creating some kind of course and students database, and i needed generic linkedlist.
i sent my work to some of my friends and all got stack overflow.
it was my mistake using recursive merge from the beginning.
i was aware of the option to change the stack size but its not possible because the program must work on default settings.
Anyway i really appreciate your help guys, i learned a lot, and definitely this is my new favorite programming forum

Well at the default of 1MB you'll probably find that in a release build that it allows for a lot more before levels of recursion before you get stack overflow. Debug builds add various check patterns etc. Release build default settings should at least do some optimisation.
Good luck anyway, you did rather well IMHO.