Sorting a linked list

[universal exports]

I'm trying to sort a singly linked list.

I have a Sort function that is called by an Insert function after each insert. The problem I'm having is that when I try to insert a third node in the link, the sort function stops the program.

void PhoneBook::Sort() 
{
Node * tmp1 = NULL;
Node * tmp2 = NULL;
Node * tmp3 = NULL;

for (int i=1; i < phonebook.m_num; i++)
{
	tmp1 = phonebook.head;
	for (tmp2 = phonebook.head->next; tmp2->next != NULL; tmp2 = tmp2->next) 
	{

		if (tmp2->data > tmp2->next->data) 
		{
			tmp3 = tmp2->next;
			tmp1->next = tmp2->next;
			tmp2->next = tmp3->next;
			tmp3->next = tmp2;
		}
		tmp1 = tmp1->next;
	}
}
}

[head] ----> [node1] -----> [node2] ------> [node3]

It is my understanding that if I want to swap node1 with node2 I need to:

A) Link node1 to node3
B) Link node2 to node1
C) Link head to node2

Anyone know why my code is not doing that?

[D80DSL3A]

The code in lines 15 - 18 is good but there is a problem with the inner for loop.
I tried your sort function on my own list and it crashes when sorting a list when the last 2 elements need to be swapped.

This is because line 17 makes tmp2->next = NULL , then tmp2 is "incremented" in the for loop making tmp2 = NULL and finally the test in the for loop tmp2->next != NULL causes the crash.

Inserting these lines after line 20 prevents the crash:

if( !tmp2->next )
	break;

The Sort() suffers from other problems as well.
1) The head value stays at the head, even if it is > head->next->data.
2) Nodes get lost. Sorting the list of values 9 7 6 4 2 produces 9 2 4 6. The Node with data = 7 gets lost. I think tmp1 is not following just behind tmp2 as expected but I'm not sure.
Hope this helps.

EDIT: Yes, problem 2 is caused by tmp1 falling out of sync with tmp2. Replacing line 20:
tmp1 = tmp1->next;
with
tmp1 = tmp2;
solves problem 2. soring 9 7 6 4 2 produces 9 2 4 6 7 leaving just problem 1.

[writetonsharma]

It would be easy if you make it recursive. Keep calling the function till you get a null. Now when the stack starts unwinding, you just have to join the nodes to the head. Think about this.