Merge Sort

Merge Sort comes in two flavors - recursive and non-recursive. The most well-known is the recursive implementation.

If the number of data items (N) is one then return the sorted list
Otherwise sort the first N/2 data items using Merge Sort
and sort the last N/2 data items using Merge Sort
Merge the two sorted sublists.

void MergeSort(int A[], int TopIndex) where A is a list of integers.
As you might have deduced from the code above most of the work is done in the Merge operation. Therefore we will create a function called Merge that will merge two sorted lists into a single sorted list.
void Merge(int InList1[], int Top1, int InList2[], int Top2, int OutList[])
Top1 and Top2 are the top indexes of InList1 and InList2 respectively.

Our driver program will, basically, generate a dataset of a certain size and then call MergeSort to sort the data. We will need several utility functions to do basic work like print out the results of the sort and to check to make sure the data is actually sorted.

void DisplayData(float DataArray[], int TopIndex);

bool CheckSorted(float DataArray[], int TopIndex);



The final program should do the following:

    Explain its purpose to the user
    
Ask the user for the number of numbers to be sorted
    
Generate a single random data set
    
Sort the data
    
Report the size of the dataset and the time required to sort or the number of comparisons or both.

Here is a MergeSort skeleton and pseudocode to give you additional help if needed.



As always the base grade for this assignment is a B+.

A good extra credit enhancement would be to ask the user how many trials he/she would like and execute the program that many times with that many data sets and write the results to a file.  This will enable us to compare the running times with respect to the size of the input.







Top of this page        
  Home page