Merge Sort

1void mergeSort(int[] arr, int left, int right) {2  if (left >= right) return;  // single element, done3  int mid = (left + right) / 2;  // split point4  mergeSort(arr, left, mid);  // sort left half5  mergeSort(arr, mid + 1, right);  // sort right half6  merge(arr, left, mid, right);  // merge the halves7}8 9void merge(int[] arr, int left, int mid, int right) {10  int[] temp = new int[right - left + 1];  // scratch buffer11  int i = left, j = mid + 1, k = 0;12  while (i <= mid && j <= right)  // compare the two fronts13    temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];  // take the smaller14  while (i <= mid) temp[k++] = arr[i++];  // leftovers15  while (j <= right)  temp[k++] = arr[j++];16  for (int x = 0; x < temp.length; x++) arr[left + x] = temp[x];  // copy back17}