I am having trouble with this assignment and was hoping I could get some help. I am not sure whether or not the output for my decomposed, unsorted, and sorted lists are correct. I'm not sure how to interpret the data in order to help justify why the big-o estimate for the merge sort is O(n log n). Any insight would be incredibly valuable as I am very lost here.
Below is the assignment followed by the code I have written
1. Write a computer program that implements the recursive merge sort.
The input to the program must be a small list of 10 to 20 elements (e.g. integer
numbers). The merge sort must produce a sorted list as an output.
The program should display the list being sorted and the sublists into which it is
recursively decomposed during the sorting process. The program must also
display the lists into which these sublists are merged to form the final sorted list.
2. Give a big-O estimate of the complexity of the merge sort algorithm that you
wrote. Justify your big-O estimate of the complexity of the merge sort algorithm
with reference to the decomposition of the unsorted list into sublists and the
subsequent merge of these sublists into the final sorted list. To this effect, use the
information displayed by your program.
#include <iostream>
using namespace std;
#define MAX_ELEMENTS 16
int a[MAX_ELEMENTS + 1]; // add 1 cause array indexing starts @ 1 for
void print(const char *msg, int low, int high)
{
cout << msg << ": ";
for(int i = low; i <= high; i++)
cout << a[i] << " ";
cout << endl;
}
void merge(int,int,int);
void merge_sort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(low,mid);
print("decomposed", low, mid);
merge_sort(mid+1,high);
print("decomposed", mid + 1, high);
merge(low,mid,high);
}
}
void merge(int low,int mid,int high)
{
int h,i,j,b[50],k;
h=low;
i=low;
j=mid+1;
print("unsorted", low, high);
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++) a[k]=b[k];
print("sorted", low, high);
}
int main()
{
const int num = MAX_ELEMENTS;
cout<<endl;
int c = 1;
a[c++] = 16;
a[c++] = 15;
a[c++] = 14;
a[c++] = 13;
a[c++] = 12;
a[c++] = 11;
a[c++] = 10;
a[c++] = 9;
a[c++] = 8;
a[c++] = 7;
a[c++] = 6;
a[c++] = 5;
a[c++] = 4;
a[c++] = 3;
a[c++] = 2;
a[c++] = 1;
merge_sort(1,num);
cout<<endl<<endl;
print("Sorted list ", 1, num);
cout<<endl<<endl<<endl<<endl;
system("pause");
}