#include<iostream.h>
#include<stdio.h>


void Merge(int *A, int first1, int last1, int last2plus1) {
  int tmp[last2plus1-first1];
  int posA=first1;
  int posB=last1+1;

  //cout<<"Entro!"<<endl;

  /* for(int i=first1;i<last2plus1;i++){
    cout<<"A["<<i<<"]= "<<A[i]<<" ";
    }*/

  for(int pos=0; pos<last2plus1-first1;pos++) {
    if( (posA<=last1) && (posB>=last2plus1 || A[posA]<=A[posB]) ) {
      tmp[pos]=A[posA++];
    }
    else {
      tmp[pos]=A[posB++];
    }
  }
  for(int pos=0; pos<last2plus1-first1;pos++) {
    A[first1+pos]=tmp[pos];  
  }

  // cout<<"Esco!"<<endl;

 /*  for(int i=first1;i<last2plus1;i++){
    cout<<"A["<<i<<"]= "<<A[i]<<" ";
    }*/


}


void MergeSort(int *A, int from_incluso, int to_escluso) {
  if(from_incluso >= to_escluso -1) return;
  MergeSort(A, from_incluso, (from_incluso+to_escluso)/2);
  MergeSort(A, (from_incluso+to_escluso)/2, to_escluso);
  Merge(A, from_incluso, (from_incluso+to_escluso)/2, to_escluso);
}

int main(int argc, char** argv) {

  int A[20];
  for (int i = 0; i < 20; i++)
    A[i] = i;

  MergeSort(A,0,20);

  for (int i = 0; i < 20; i++)
    cout << A[i] << endl;

  return 0;
}