Linked List Merge Sort Intended Behavior?

[k3rb3ros]

Hey guy's I have been trying to implement merge sort for linked list's. It works for reversed numbers, but when trying to sort random data it does not sort correctly. As well as when sorting two or more instances of the same number ie you would expect {1, 2, 3, 4 , 1, 2, 3, 4} to sort as {1, 1, 2, 2, 3, 3, 4, 4} but it returns as {1, 2, 3, 4 , 1, 2, 3, 4}. Is there something wrong with my implementation of the algorithm or is this actually how merge sort works?

Please note my code is broken up into a bunch of helper functions if you think the problem lies in a function that I didn't include I will gladly include it.

Merge Sort:

node* mergesort(node* left, ofstream& outf)
{
	outf << "Merge sort ";//all outf entries are for debugging purposes
	node* right;
	outf << length(left) << " entries" << endl;
	if(left -> link != nullptr)// if list isn't shorter then 1 entry then sort it...
	{
		right = split(left); //create the right sublist
		//Call merge sort recursively for both the left and the right sublists
		outf << "Left : ";
		showlist(left, outf);
		outf << "Right : ";
		showlist(right, outf);
		return merge(mergesort(left, outf), mergesort(right, outf)); //Merge the two sorted lists and return them as one sorted list
	}
	outf << "returning  " << left -> value << endl;
	return left; //otherwise list is 1 long or shorter so return it
}

Merge:

node* merge(node* list1, node* list2)
{
	node* tmp = nullptr; //create a node to find the end of a list without losing its head
	while(list1 != nullptr ||  list2 != nullptr)
	{
		if(list1 != nullptr && list2 != nullptr)//if both lists have at least 1 node... continue with merge
		{
			if(list1 -> value  <= list2 -> value)
			{
				tmp = list1;
				while (tmp -> link != nullptr) tmp = tmp -> link; //Advance to the end of the list
				tmp -> link = list2; //Set the end of list 1 to link to list 2
				return list1; //return the merged list
			}
			else
			{
				tmp = list2;
				while (tmp -> link != nullptr) tmp = tmp -> link; //Advance to the end of the list
				tmp -> link = list1; //Set the end of list 2 to link to list 1
				return list2; //return the merged list
			}
		}
		else if(list1 = nullptr)return list2; //if list 1 is empty merging  is unneccesary so return list 2
		else return list1;//otherwise the only remaining possibility is list 2 is empty so return list 1
	}
}

Split:

node* split(node* list)
{
	node* pivot;
	node* right;
	int i;
	if(list -> link != nullptr) //If list is longer then one node continue...
	{
		pivot = list;
		for(i=1; i<(length(list))/2; i++) pivot = pivot -> link; //navigate to the center of the list
		right = pivot -> link; //Create the right sublist
		pivot -> link = nullptr; //Split it from the left sublist
		return right; //return head of right
	}
	else return nullptr; 	
}

Length:

int length(node* list)
{
	int i = 0;
	if(!empty(list))
	{
		while(list != nullptr)
		{
		i++;
		list = list -> link;
		}
		return i;
	}
	else return 0; //If list is empty length is 0
}

[helios]

You're merging, but there doesn't appear to be any sorting going on.
The algorithm goes like this:

container merge_sort(container c){
    if (c.size()<=2){
        if (c.size()==2 && c[1]<c[0])
            c.reverse();
        return c;
    }
    return merge(merge_sort(c.first_partition()),merge_sort(c.second_partition()));
}

EDIT: After looking a bit at merge(), I see that it's incorrect. If list1 is empty inside the loop and you return list2, you'll get incorrect behavior if every element of list1 is < than the first element of list2. The same will happen if list2 is empty and you return list1. I haven't checked the rest, but this whole thing reeks of memory leaks.

[k3rb3ros]

I rewrote merge as follows and everything works correctly now.

node* merge(node* list1, node* list2)
{
	node* tmp = nullptr; //create a node to find the end of a list without losing its head
	node* newl = nullptr;
	if(list1 == nullptr) return list2; //list1 is empty no merging is necessary return list 2  
	else if(list2 == nullptr) return list1; //list 2 is empty...
	else
	{
		if (list1 -> value < list2 -> value) //compare the first nodes
		{
			newl = list1;
			list1 = list1 -> link;
			tmp = newl;
		}
		else 
		{
			newl = list2;
			list2 = list2 -> link;
			tmp = newl;
		}
		while(list1 != nullptr && list2 != nullptr) //special sauce is here
		{
			if(list1 -> value < list2 -> value)
			{
				tmp -> link = list1;
				tmp = tmp -> link;
				list1 = list1 -> link;
			}
			else
			{
				tmp -> link = list2;
				tmp = tmp -> link;
				list2 = list2 -> link;
			}
		} //end while
		if(list1 == nullptr)
		{
			tmp -> link = list2;
		}
		else tmp -> link = list1;
		return newl;
	}
}