static void merge(int [] A, int lo, int mid, int hi) {

//This method is used by merge_sort to combine two sorted sub_arrays

final int maxsize = 4096;

int [] temp = new int [maxsize];

int i,NextLeft,NextRight;

NextLeft = lo;

i = lo;

NextRight = mid;

while ((NextLeft < mid) && (NextRight < hi)) {

count+=3; cmprs++; //counting compares 2 for the while loop, 1 for the if

if (A[NextLeft] < A[NextRight]) {

temp[i] = A[NextLeft];

NextLeft++;

i++;

}

else {

temp[i] = A[NextRight];

NextRight++;

i++;

}

}

count++;

//append the remaining elements from the left or right subarray to the temp array

while (NextLeft < mid) {

temp[i] = A[NextLeft];

NextLeft++;

i++;

count++;

}

while (NextRight < hi) {

temp[i] = A[NextRight];

NextRight++;

i++;

count++;

}

count+=2; //one for the exit of each of the last two while loops

//copy back into A

for (i= lo; i < hi; i++) {

A[i] = temp[i];

swaps++;

count++;

}

count++;

} // end merge

public static void mergeSort(int [] A, int lo, int hi) {

int mid;

count++;

if ((hi-lo) > 1) {

mid = (hi + lo)/ 2;

mergeSort(A,lo,mid);

mergeSort(A,mid,hi);

merge(A,lo,mid,hi);

}

} //end mergeSort