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

This code is a prime candidate for a loop:

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;

The Big-O value of a sort has to do with the number of "things" you have to do to sort n numbers. Usually that "thing" is a comparison between two elements and sometimes that "thing" is a swap and sometimes it's both. I think, generally what to keep track of is the number of comparisons between elements. It's certainly not the only thing that contributes to sorting time, but I would imagine that that is what your teacher is looking for.

So set up a comparison counter, probably make it a global variable, and initialize it to 0. Every time you compare the values of two elements of the array with the == or > or < operator, increment the counter. Look up the Big-O value of the sort online and calculate it for a given n. Compare it to your comparsion counter and see whether they are about the same.

Thank you very much for the reply, but I don't think I am actually supposed to do an estimate myself. Just justify the one given, using the information output by my program. At least, that is how my instructor made it sound.

Thank you very much for the reply, but I don't think I am actually supposed to do an estimate myself. Just justify the one given, using the information output by my program. At least, that is how my instructor made it sound.

Big-O is based on comparison counts. If you don't keep track of any comparison counts or some type of count and compare it the known Big-O count and output the different results, what program output could possibly "justify" the Big-O formula? What I suggested is not doing an "estimate" yourself. You are making an exact count and comparing it to the known "estimate" (nlogn) of the merge sort.

I don't think that is what I am supposed to do. It says in the assignment to justify the estimate using the output from my program for reference. I'm just not sure how to do that because the program's output isn't as clean cut as a tree would be.

Lets analyze what the mergesort do.

The first Function you've written

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

it simply spit the array of size n from mid and do it untile (low < high).
if your problem size ( in your case: the size of the array ). is n in the next iteration (when the function is recursed). is (n/2) i.e. first half and (n/2) second half. . the next time function is called it would become n/4 and n/4.

This means what you are doing is
T(n) = T(n/2) + T(n/2).

not lets come to merge.
after the merge_sort return you call the merge function
which compares the two sub arrays, and modify the original one (i.e. it takes n steps) isn't it ?

so the the recurrence relation becomes.
T(n) = 2T(n/2) + n.

Now what we need to do is to solve this (three method exists to solve this relation).
1. Recursion Tree method.
2. Substitution method.
3. Master Theoram.

Solve it yourself. (it required little mathematics).
what you'll get in the end will be n(lgn)+ n + 1.
lg = logarithm of base 2.
The Big O will be n(lgn).

This article has been dead for over six months. Start a new discussion instead.