MergeSort on a List issue

[unsensible]

Hello everyone. I had question about the "MergeSort algorithm".

In this algorithm, you are meant to split a data structure (in this case a list) in half, and then merge the sub-lists back together in sorted order. This can also be done recursively on the sublists.

When I run this code, It successfully splits the lists and merges them back together. However, the list is still not sorted. Could anyone please look into this for me? It would be much appreciated.

Here is my code:

#ifndef MYLIST_H
#define MYLIST_H

using namespace std;

template <typename T> 
class mylist : public list< T >
{
public: 

	mylist();
	mylist(T *arr1,T *arr2);

	mylist < T > mergeSort(void);

};

template <typename T>
mylist< T >::mylist(): list< T >()
{

}
template <typename T>
mylist< T >::mylist(T *arr1, T *arr2): list< T >(arr1, arr2)
{

}
template <typename T>
mylist< T > Merge(mylist< T > &L1, mylist< T > &L2)
{
	mylist< T > List;//list to be returned
	typename list< T >::iterator it1 = L1.begin();
	typename list< T >::iterator it2 = L2.begin();

	while(it1 != L1.end() && it2 != L2.end())//while neither lists have ended
	{
		if((*it1) < (*it2))//if one is less than 2
		{
			List.push_back(*it1);//then push 1
			it1++;
		}
		else
		{
			List.push_back(*it2);//otherwise push 2
			it2++;
		}
	}//BUT, after L1 or L2 is at end
	if(it1 == L1.end()) //see if 1 is at end, if so then
	{
		while(it2 != L2.end())//while there are still elements
		{
			List.push_back(*it2);//then push remainder of 2 onto list
			it2++;
		}
	}
	else//otherwise 
	{
		if(it2 == L2.end())
		{
			while(it1 != L1.end())//while there are still elements
			{
				List.push_back(*it1);//then push remainder of 1 onto list
				it1++;
			}
		}
	}
	return(List);
}

template <typename T>
void split(mylist< T > &L, mylist< T > &L1, mylist< T > &L2)
{
	typename list<int>::iterator iter;
	//check for one or 0
	int siz = L.size();
	if(siz > 1)//make sure there is more than 1 element
	{
		siz = siz / 2;//get middle
		int i = 0;
		for (iter = L.begin(); i < siz; iter++)//loop through first half
		{
			L1.push_back(*iter);//push first half on separate list
			i++;
		}
		for(;iter != L.end();iter++)//loop through second half
		{
			L2.push_back(*iter);//push second half
		}
	}
}

template <typename T>
mylist< T > mylist< T >::mergeSort(void)
{
	mylist < T > SortedList;
	int siz = (*this).size();
	if(siz > 1)//make sure there is more than 1 element
	{
		mylist< T > L1;
		mylist< T > L2;

		split((*this),L1,L2);//call split Template function
		L1.mergeSort();//recursive calls
		L2.mergeSort();//recursive calls
		SortedList=Merge(L1,L2);//call Merge Template function
	}
	return(SortedList);//or I could just return (*this) and remove
}						//the sortedList declaration

template <typename T>
void print(mylist < T > List)
{
	typename mylist< T >::iterator iter;

	for (iter = List.begin(); iter != List.end(); iter++)
	{
		cout<<*iter<<" ";
	}
	cout << endl;
}
#endif 

My main test program:

#include "stdafx.h"
#include "targetver.h"
#include <iostream>
#include <list>
#include "mylist.h"


using namespace std;

int main()
{
	int arr[]={8,7,6,5,4,3};
	mylist<int> List(arr,arr+6);
	mylist<int>::iterator iter;
	mylist<int> List2;
	mylist<int> List3;
	
	/*
	mylist<int> L3;
	split(List,List2,List3);
	print(List2);                   //Test code
	print(List3);					//uncomment to test
	L3 = Merge(List2,List3);
	print(L3);
	*/



	List = List.mergeSort();	//if testing above, then comment this out

	print(List);//function to print list

	
	system("pause");

	return 0;
}

[cire]

I think the biggest problem with your code is that mergeSort doesn't modify the list on which it is invoked and you ignore the return value when you call the function recursively.

[keskiverto]

Your mergeSort does not modify "this", it returns a "SortedList". However, if "this" has only one element, you return empty "SortedList". That is a mistake.

Better yet, you call mergeSort() on "L1" and "L2", but don't store the return values. Then you merge the unsorted lists. This error actually masks the other error.

[unsensible]

Thanks a lot guys. Works like a charm! Sorry again cire.

Only a few minor fixes in the mergesort function below

template<typename T>
mylist< T > mylist< T >::mergeSort(void)
{
	mylist < T > SortedList;
	int siz = (*this).size();
	if(siz > 1)//make sure there is more than 1 element
	{
		mylist< T > L1;
		mylist< T > L2;

		split((*this),L1,L2);//call split function over and over until there is only 1 element left
		L1=L1.mergeSort();//recursive calls
		L2=L2.mergeSort();//recursive calls
		*this=Merge(L1,L2);//call Merge function and store the list 
	}
	return(*this);//returns the correctly sorted array
}						

[keskiverto]

Frank had an opinion about men, who wear both belt and suspenders.

Line 4: unused variable SortedList.

Line 14 reveals that the list itself is sorted, but now you make copies on lines 12, 13, and 16 too.

I would choose only one: either (1) return a sorted copy and the list does not change, or (2) list is sorted after the call and return is void.