Merge Sort Problem

unsensible (78)
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
#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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#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 (8284)
Please do not cross-post to multiple forums.

http://www.cplusplus.com/forum/beginner/111092/
unsensible (78)
Sorry, I figured this problem may have been a bit complex for the beginner section so I figured I moved it to here.
Topic archived. No new replies allowed.