Top-down implementation of merge sort.

mergesort.java

void mergeSort(int[] a, int[] b, int first, int last) {
  if (first < last) {
    int mid = (first + last) / 2;
    mergeSort(a, b, first, mid - 1);
    mergeSort(a, b, mid, last);
    merge(a, b, first, mid, last);
    copyBtoA(b, a, first, last);
  }
}

void merge(int[] a, int[] b, int first, int mid, int last) {
  int left = first;
  int right = mid;
  
  for (int i = first; i < last; i++) {
    if (i < mid && (right > last || a[left] <= a[right])) {
      b[i] = a[left];
      left++;
    } else {
      b[i] = a[right];
      right++;
    }
  }
}

void copyBtoA(int[] b, int[] a, int first, int last) {
  for (int i = first; i < last; i++) {
    a[i] = b[i];
  }
}