### MergeSort on a List issue

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:

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121`` ``````#ifndef MYLIST_H #define MYLIST_H using namespace std; template class mylist : public list< T > { public: mylist(); mylist(T *arr1,T *arr2); mylist < T > mergeSort(void); }; template mylist< T >::mylist(): list< T >() { } template mylist< T >::mylist(T *arr1, T *arr2): list< T >(arr1, arr2) { } template 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 void split(mylist< T > &L, mylist< T > &L1, mylist< T > &L2) { typename list::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 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 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:

 ``1234567891011121314151617181920212223242526272829303132333435363738`` ``````#include "stdafx.h" #include "targetver.h" #include #include #include "mylist.h" using namespace std; int main() { int arr[]={8,7,6,5,4,3}; mylist List(arr,arr+6); mylist::iterator iter; mylist List2; mylist List3; /* mylist 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; } ``````
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.
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.
Thanks a lot guys. Works like a charm! Sorry again cire.

Only a few minor fixes in the mergesort function below

 ``123456789101112131415161718`` ``````template 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 } ``````
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.
Topic archived. No new replies allowed.