#include<iostream>
using namespace std;
void merge(int A[],int n1,int index1,int B[],int n2, int index2,int c[],int index3)
{
 while(n1 && n2)
 {
  if(A[index1]<B[index2])
  {
   c[index3]=A[index1];
   index3++;
   index1++;
   n1--;
  }
  else
  {
   c[index3]=B[index2];
   index3++;
   index2++;
   n2--;
  }
 }
 while(n1)
 {
  c[index3]=A[index1];
  index3++;
  index1++;
  n1--;
 }
 while(n2)
 {
  c[index3]=B[index2];
  index2++;
  index3++;
  n2--;
 }
}
void mergepass(int A[],int N, int L,int B[])
{
 int j,lb;
 int q,s,r;
 q=N/(2*L);//total pair if arrays to be merged
 s=2*L*q;//total number of sorted pair in long array{considered elements}
 r=N-s;//r is residual elements
 for(j=0;j<q; j++)
 {
  lb=2*j*L;//lower bund of index to be passed for merging
  merge(A,L,lb,A,L,lb+L,B,lb);
 } 
 if(r<=L)//if i subarray remaining
 {
  for(j=0;j<r; j++)
  {
   B[s+j]=A [s+j];//copying residual elements dirctly
  }
 }
 else//if two subarrays of unequal length
 {
  merge(A,L,s,A,r-L,s+L,B,s); 
 }
}
void merge_sort(int A[],int N)
{
 int l=1,B[12];
 while(l<N)
 {
  mergepass(A,N,l,B);
  mergepass(B,N,2*l,A); 
  l=4*l;
 }
}
int main()
{
 int A[]={44,33,11,55,77,90,40,60,99,22,88,66};
 merge_sort(A,12);
 for(int i=0; i<12; i++)
 {
  cout<<A[i]<<"t";
 }
 return 0;
}>