#include <iostream.h>
 
 
int *Arr, maxSize;
 
void createArr()
{
  cout<<"\n\n Enter the maximum size of array : ";
  cin>>maxSize;
  Arr = new int[maxSize];
}
 
void fillArr()
{
  cout<<"\n\n Enter the elements of the array (to be sorted) (maximum "
      <<maxSize<<")";
  int i = 0;
  for (i=0; i<maxSize; i++)
    cin>>Arr[i];
}
 
int* merge(int* l, int* r, int lS, int rS)
{
  int* res, lIndex = 0, rIndex = 0, i = 0, totalSize;
  totalSize = lS + rS;
 
  res = new int[totalSize];
 
  for(i = 0; lIndex != lS && rIndex != rS; i++)
    {
      if (l[lIndex] < r[rIndex])
	{	
	  res[i] = l[lIndex];
	  lIndex++;
	}
      else 
	{
	  res[i] = r[rIndex];
	  rIndex++;
	}
    }
  for(i; i < totalSize; i++)
    {
      if (lIndex < lS)
	{
	  res[i] = l[lIndex];
	  lIndex++;
	}
      else if (rIndex < rS)
	{
	  res[i] = r[rIndex];
	  rIndex++;
	}
    }
  return res;
}
 
int* append (int* l, int* r, int lS, int rS)
{
  int *res, totalSize, i=0, j=0;
 
  totalSize = lS + rS;
 
  res = new int[totalSize];
 
  for (i=0; i < lS; i++)
    {
      res[i] = l[i];
    }
  for (i = lS; i < totalSize; i++)
    {
      res[i] = r[j];
      j++;
    }
  return res;
}
 
int* mergeSort (int* array, int length)
{
  if (length <= 1)
    return array;
 
  int *left, *right, *final, middle = 0, i = 0, j = 0;
 
  middle = length/2;
 
  left = new int[middle];
  right = new int[length-middle];
 
  for (i = 0; i < middle; i++)
    {
      left[i] = array[i];
    }
 
  for (i = middle; i < length; i++)
    {
      right[j] = array[i];
      j++;
    }
 
  left = mergeSort(left, middle);
  right = mergeSort(right, (length-middle));
 
  if (left[middle-1] > right[0])
    final = merge (left, right, middle, length-middle);
  else
    final = append (left, right, middle, length-middle);
 
  return final;
}
 
 
int main()
{
  int choice = 0, *sorted, i=0;
  while (choice != 4)
    {
      cout<<"\n\n Enter choice :"
	  <<"\n 1. Create array."
	  <<"\n 2. Enter elements in array."
	  <<"\n 3. Sort the array using Mergesort."
	  <<"\n 4. Exit. ";
      cin>>choice;
 
      switch(choice)
	{
	case 1:
	  createArr();
 
	  break;
	case 2:
	  fillArr();
	  break;
	case 3:
	  sorted = mergeSort(Arr, maxSize);
	  cout<<"\n\n The sorted array is : \n";
	  for (i=0; i < maxSize; i++)
	    {
	      cout<<sorted[i]<<" ";
	    }
	  break;
	case 4:
	  break;
	default:
	  cout<<"\n Invalid choice entered.";
	  break;
	}
    }
}