#include<iostream>
#include<string>

using namespace std;

// This file contains implementations for mergeSort for arrays.


void swap(int a[], int i, int j) { // A general swap function.
  int temp= a[i];
  a[i]= a[j];
  a[j]= temp;
}

void merge (int A[], int a, int mid, int b) {
 if (a < b && mid >= a && mid <= b) {
     int tA[b-a+1]; // temporary array -- scratch space O(n)
     int i= a; int j= mid+1; int ti= 0;
     while(i <=mid && j <= b) { // Invariant: tA[0..ti) is sorted and
      if (A[i] > A[j]) {tA[ti]= A[j]; j++;} // tA[0..ti)<=A[i..mid], A[j..b]
      else {tA[ti]= A[i]; i++;}  // copy elements into it, preserving the
      ti++;                            // relative order...
      }
        if (i < mid+1) {  // Complete the copy in the case that one side
         for (; i< mid+1; i++){ // is used up before the other
          tA[ti]= A[i]; ti++; }
       }
      else {
        for (; j< b+1; j++){
         tA[ti]= A[j]; ti++;}
      }
   for(int k= a; k< b+1; k++)  A[k]= tA[k-a]; // Copy back to A
}}


void mergeSort(int A[], int first, int last){ // Need to keep data for call..
 // sorts the array between A[first..last]
   if (first< last) { // only do something if the portion has more than item
     mergeSort (A, first, (first+last)/2); // split and sort each half
     mergeSort (A, (first+last)/2 + 1, last);
     merge(A, first, (first+last)/2, last); // merge the sorted halves.
   } 
}