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");
}
```