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