#include <stdio.h>
#include <stdlib.h>
void mergeSort(int a[],int start,int end);
void merge(int a[],int start[],int end[] );
int main()
{
  int array[14]= { 24,2,17,5,28,11,10,9,19,14,17,8,12,21 },n=14,i,test[3] = {2,1,3};
  mergeSort(array,0,n-1);
  
  for(i=0;i<n;i++)
  {
    printf("%d\n",array[i]);
  }
  return 0;
}
void mergeSort(int a[],int first,int last)
{
  printf("first = %d  last = %d \n",first,last);
  if(first>last)
    return;
  if(first == last)
    return;
  if(first == last-1)
  {
    if(a[first] < a[last])
      return;
    else
    {
      int temp = a[first];
      a[first] = a[last];
      a[last] = temp;
      return;
    }
  }
  
  int start[3],end[3];
  start[0] = first,start[1] = first + (last - first + 2)/3 , start[2] = first + ( (last - first + 2) * 2) /3;
  end[0] = start[1] -1;end[1] = start[2] -1 ;end[2] = last;
  //printf("abcd \n");
  mergeSort(a,start[0],end[0]);
  mergeSort(a,start[1],end[1]);
  mergeSort(a,start[2],end[2]);
  
  merge(a,start,end);
}
void merge(int a[],int start[],int end[])
{
  int index[3],p,i=0;
  index[0]= start[0];index[1] = start[1] ;index[2] = start[2]; p = 0;
  int tempArray[20]; // this could be replaced by dynamic allocation of array using pointers
  while(p <= end[2] - start[0])
  {
    int min = 65530, in = -1;
    for(i=0;i<3;i++)
    {
      if(a[ index[i] ] < min && index[i] <= end[i])
      {
	min = a[ index[i] ];
	in = i;
      }
    }
    tempArray[p] = min;
    p++;
    index[ in ]++;
    
  }
  for(i=start[0];i<=end[2];i++)
  {
    a[i] = tempArray[i - start[0] ];
  }
}