MergeSort.java

void merge(int dataCollection[], int left, int mid, int right) {
  // Find size of two sub arrays to be merged
  int n1 = mid - left + 1;
  int n2 = right - mid;

  int leftTempArray[] = new int[n1];
  int rightTempArray[] = new int[n2];

  // Set data to temp arrays
  for (int i = 0; i < n1; ++i)
    leftTempArray[i] = dataCollection[left + i];
  for (int j = 0; j < n2; ++j)
    rightTempArray[j] = dataCollection[mid + 1 + j];

  // Initial indexes of first and second subarrays
  int i = 0, j = 0;

  // Initial index of merged subarray array
  int k = left;
  while (i < n1 && j < n2) {
    if (leftTempArray[i] <= rightTempArray[j]) {
      dataCollection[k] = leftTempArray[i];
      i++;
    }
    else {
      dataCollection[k] = rightTempArray[j];
      j++;
    }
    k++;
  }

  // Copy remaining elements of leftTempArray[]
  while (i < n1) {
    dataCollection[k] = leftTempArray[i];
    i++;
    k++;
  }

  // Copy remaining elements of rightTempArray[]
  while (j < n2) {
    dataCollection[k] = rightTempArray[j];
    j++;
    k++;
  }
}

void sort(int dataCollection[], int left, int right) {
  if (left < right) {
    // Find the middle value
    int mid =left+ (right-left)/2;

    // Sort first and second halves
    sort(dataCollection, left, mid);
    sort(dataCollection, mid + 1, right);

    // Merge the sorted halves
    merge(dataCollection, left, mid, right);
  }
}