I'm having difficulties thinking through the logic of my natural mergesort program. I think I have the split working correctly, but my merge doesn't seem to be working at all, and the pseudocode in my book and what I've found so far on the web is fuzzy.
This is a natural mergesort, not your typical binary mergesort, in the sense that it needs to take into account "sublists," or elements in the list which are increasing (i.e. already sorted).
This is what I have so far. I suspect my problem is in the merge function.
Any help you could render would be greatly appreciated! :)
/******************************************************************************
* Program:
* Assignment 18, Natural Mergesort Program
* Summary:
* Gets a filename from the command line, and reads in numbers, inserting
* them at the beginning of a linked list. The program then sorts the list
* with a natural mergesort, using the external sort algorithm. After
* sorting, the list contents are displayed.
******************************************************************************/
#include <iostream>
#include <fstream>
#include <list>
using namespace std;
///////////////////////////////////////////////////////////////////////////////
// main
///////////////////////////////////////////////////////////////////////////////
/**** Prototypes used in main *****/
list < int > buildList(string filename);
void mergesort(list < int > &myList);
void split(list < int > &myList, list < int > &sublist1,
list < int > &sublist2);
list < int > merge(list < int > &sublist1, list < int > &sublist2,
int &numSublists);
void display(list < int > &myList);
/******************************************************************************
* main
* Desc:
* Gets a filename from the command line, and reads in numbers, inserting
* them at the beginning of a linked list. The program then sorts the list
* with a natural mergesort, using the external sort algorithm. After
* sorting, the list contents are displayed.
******************************************************************************/
int main(int argc, char* argv[])
{
string filename;
//Check for proper usage
if (argc != 2)
{
cout << "Usage: <executable> <data file>\n";
exit(1);
}
else //input is good
{
filename = argv[argc - 1];
}
/* Populate a linked list with the numbers, perform a natural merge sort
on the list, and display the sorted list */
list < int > numbers = buildList(filename);
mergesort(numbers);
display(numbers);
return 0;
}
/******************************************************************************
* buildList
* Desc: Reads in numbers from a file and populates a linked list with the
* numbers. The linked list is then returned from the function.
* Input: string filename
* Return: Linked list of integers from the file (myList)
******************************************************************************/
list < int > buildList(string filename)
{
ifstream inStream;
list < int > myList;
//open file and check for success
inStream.open(filename.c_str());
if (inStream.fail()) //file failed to open
{
cout << "Unable to open file \"" << filename
<< "\" in function buildList()\n";
exit(1);
}
else //successfully opened file
{
int number; //numbers read in from file
//push on all numbers from file onto vector
while (inStream >> number)
{
myList.push_front(number);
}
inStream.close();
}
return myList;
}
/******************************************************************************
* mergesort
* Desc: Performs a natural merge sort, using the external sort algorithm, on
* a user-specified linked list.
* Input: Linked list to be sorted (myList)
* Big-O: O(n log2 n) <worst case, average case>
******************************************************************************/
void mergesort(list < int > &myList)
{
list < int > split1;
list < int > split2;
int numSublists = 0;
do //Do while numSublists is greater than 1 (We have more to sort)
{
//split myList into two lists
split(myList, split1, split2);
//merge corresponding sublists in split1 and split2 back into myList.
myList = merge(split1, split2, numSublists);
} while (numSublists > 1);
}
void split(list < int > &myList, list < int > &split1,
list < int > &split2)
{
split1.clear();
split2.clear();
list < int > *target = &split1;
list < int > ::iterator listIter = myList.begin();
//split list F into lists F1 and F2 by copying natural sorted subfiles of F alternately to F1 and F2
//WHILE the end of F has not been reached:
int prev = *listIter;
target->push_back(prev);
++listIter;
int current;
while (listIter != myList.end())
{
current = *listIter;
//copy a sorted subfile of F into F1 as follows: repeatedly read an element of F and write it into F1 until the next element in F is smaller than this copied item or the end of F is reached.
if (current < prev & listIter != myList.end())
{
//switch target
if (target == &split1)
{
target = &split2;
}
//If the end of F has not been reached, copy the next sorted subfile of F into F2 in a similar manner
else
{
target = &split1;
}
}
//write to target
target->push_back(current);
prev = current;
++listIter;
}
}
list < int > merge(list < int > &split1, list < int > &split2,
int &numSublists)
{
list < int > myList; //our newly merged list
list < int > ::iterator iter1 = split1.begin(); //iterator for sublist1
list < int > ::iterator iter2 = split2.begin(); //iterator for sublist2
numSublists = 0; //reset numSublists for this list
//While we have not reached the end of either split1 or split2
int prev1 = *iter1;
int prev2 = *iter2;
++iter1;
++iter2;
int current1;
int current2;
while (iter1 != split1.end() && iter2 != split2.end())
{
current1 = *iter1;
current2 = *iter2;
//WHILE no end of a sublist in F1 or in F2 has been reached
while (current1 > prev1 && current2 > prev2)
{
//If the next element in F1 is less than the next element in F2
if (current1 > current2)
{
//then Copy the next element from F1 into F
myList.push_back(*iter1);
}
else
{
//copy the next element from F2 into F
myList.push_back(*iter2);
}
prev1 = current1;
prev2 = current2;
++iter1;
++iter2;
}
//If the end of a subfile in F1 has been reached
if (iter1 == split1.end())
{
//Then copy the rest of the corresponding subfile in F2 to F
while (current2 > prev2 && iter2 != split2.end())
{
myList.push_back(current2);
prev2 = current2;
++iter2;
current2 = *iter2;
}
}
else
{
//copy the rest of the corresponding subfile in F1 to F
while (current1 > prev1 && iter1 != split1.end())
{
myList.push_back(current1);
prev1 = current1;
++iter1;
current1 = *iter1;
}
}
prev1 = current1;
prev2 = current2;
++iter1;
++iter2;
//Increment numSubfiles by 1
++numSublists;
}
//Copy any subfiles remaining in F1 or F2 to F, incrementing numSubfiles by 1 for each
return myList;
}
/******************************************************************************
* display
* Desc: Displays the contents of a linked list.
* Input: Linked list whose contents will be displayed (myList)
******************************************************************************/
void display(list < int > &myList)
{
list < int > ::iterator listIter = myList.begin();
while (listIter != myList.end())
{
cout << *listIter << ' ';
++listIter;
}
cout << endl;
}