I have one problem which I really can't solved after two weeks try. The questions are as below:

1. Write a program in C++ using any computer system. The program is required to implement recursion version of mergesort algorithm on an array of integers(numeric data). Add a counter in appropriate location of the implementation to count the number of times major operations (comparison, data moves)are performed in the algorithm. Run the program using various experimental dataset and try to find and run the worst case, average case, and best case (if any).

Using the coding below for this question, I just don't know where to put the counter so to get the result.

#include<iostream>

using namespace std;

const int size=6;

void mergesort(int [],int,int);
void merge(int [],int,int,int);


void main()
{
    int number[size];
    int i;
    for(i=0;i<size;i++)
    {
        cout<<"enter the number "<<i<<":";
        cin>>number[i];
    }

    mergesort(number,0,size-1);
    cout<<"\n\nList of sorted array : ";
    for(i=0;i<size;i++)
        cout<<number[i]<<"\t";

}

void mergesort (int Array[size], int first, int last)
{
    int mid;


        if(first<last)
        {
            mid=(first+last)/2;
            mergesort(Array,first,mid);
            mergesort(Array,mid+1,last);
            merge(Array,first,mid,last);
        }
}

void merge(int Array[size], int first, int mid, int last)
{
    int temp[size];
    int first1=first;
    int last1=mid;
    int first2=mid+1;
    int last2=last;
    int index=first1;

    for(; (first1<=last1) && (first2<=last2); ++index)
    {
        if (Array[first1]<Array[first2])
        {
            temp[index]=Array[first1];
            ++first1;
        }
        else
        {
            temp[index]=Array[first2];
            ++first2;
        }
    }

    for (; first1<=last1;++first1,++index)
        temp[index]=Array[first1];

    for (; first2<=last2; ++first2, ++index)
        temp[index]=Array[first2];

    for(index=first; index<=last;++index)
        Array[index]=temp[index];

}


2 Write a program in C++ using any computer system. The program is required to implement iterative version of mergesort algorithm on an array of integers(numeric data). Add a counter in appropriate location of the implementation to count the number of times major operations (comparison, data moves)are performed in the algorithm. Run the program using various experimental dataset and try to find and run the worst case, average case, and best case (if any).

The same, consider the coding below:

// file msort.h
// merge sort

#ifndef MergeSort_
#define MergeSort_

template<class T>
void Merge(T c[], T d[], int l, int m, int r)
{// Merge c[l:m]] and c[m:r] to d[l:r].
   int i = l, // cursor for first segment
       j = m+1, // cursor for second
       k = l; // cursor for result

   // merge until i or j exits its segment
   while ((i <= m) && (j <= r))
      if (c[i] <= c[j]) d[k++] = c[i++];
      else d[k++] = c[j++];

   // take care of left overs
   if (i > m) for (int q = j; q <= r; q++)
                 d[k++] = c[q];
   else for (int q = i; q <= m; q++)
           d[k++] = c[q];
}

template<class T>
void MergePass(T x[], T y[], int s, int n)
{// Merge adjacent segments of size s.
   int i = 0;
   while (i <= n - 2 * s) {
      // merge two adjacent segments of size s
      Merge(x, y, i, i+s-1, i+2*s-1);
      i = i + 2 * s;
      }

   // fewer than 2s elements remain
   if (i + s < n) Merge(x, y, i, i+s-1, n-1);
   else for (int j = i; j <= n-1; j++)
           // copy last segment to y
           y[j] = x[j];
}

template<class T>
void MergeSort(T a[], int n)
{// Sort a[0:n-1] using merge sort.
   T *b = new T [n];
   int s = 1; // segment size
   while (s < n) {
      MergePass(a, b, s, n); // merge from a to b
      s += s;
      MergePass(b, a, s, n); // merge from b to a
      s += s;
      }
}

#endif


//filename : msort.cpp
// test iterative version of merge sort

#include <iostream.h>
#include "msort.h"

void main(void)
{
   int y[10] = {10,7,8,9,4, 2, 3, 6, 5,1};
   MergeSort(y,10);
   for (int i=0; i< 10; i++) cout << y[i] << ' ';
   cout << endl;
}


For the above coding, there are four different types of dataset to test for the performance. The four different dataset are as examples below:

first set : random array (e.g. 32, 52, 35, 89, 12, 15)
second set : sorted array (e.g. 1, 2, 3, 4, 9, 10)
third set : inverse array (e.g. 101, 98, 50, 32, 10, 5)
fourth set : partial sorted array (e.g. 1, 20, 22, 47, 45, 46)


So, please advise me where to put the counter so to obtain the result, and for the conclusion, I want to know which method (recursion version or iterative version) is getting the better performance. Also, I want to know how many steps are taken (counters' value) for recursion version and iterative version of the algorithm, for example :

(recursion version)
data moves : 18
comparison : 25

(iterative version)
data moves : 20
comparison : 21

The values above are an example value only.

I know that this is a very long question and is not a quite an easy questions, but I really hope that whoever have knowledge in this thing would reply me, thank you.