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;
}
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!!!! :)