stack overflow in merge sort of linkedlist

This is a discussion on stack overflow in merge sort of linkedlist within the C++ Programming forums, part of the General Programming Boards category; hello everyone, I have created a template linked list, and im using merge sort to sort it. the problem is ...

  1. #1
    Registered User
    Join Date
    Jun 2011
    Posts
    4

    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;
    }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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).
    Last edited by iMalc; 06-17-2011 at 01:55 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Jun 2011
    Posts
    4

    you totally solved my problem

    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!!!!

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Jun 2011
    Posts
    4
    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.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,330
    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

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Jun 2011
    Posts
    4
    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

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Quick Sort - stack overflow
    By ButterCup in forum C Programming
    Replies: 7
    Last Post: 03-22-2010, 08:31 AM
  2. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 05:48 PM
  3. recursive quick sort - stack overflow
    By Micko in forum C Programming
    Replies: 9
    Last Post: 01-01-2005, 04:51 PM
  4. merge sort and selection sort and time spent on both
    By misswaleleia in forum C Programming
    Replies: 3
    Last Post: 06-04-2003, 02:24 PM
  5. linkedlist sort
    By Unregistered in forum C++ Programming
    Replies: 4
    Last Post: 03-16-2002, 11:10 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21