归并排序

public static void sort(int[] arr, int left, int right) { if (left < right) { // 中间值  int mid = (left + right) / 2;  // 左边到中值排序并合并  sort(arr, left, mid);  // 中值到右边排序并合并  sort(arr, mid + 1, right);  // 左边和右边合并, 每个递归过程结束，弹栈后左边和右边都会内部有序  // 左数组长度  int leftLen = mid - left + 1;  // 右数组长度  int rightLen = right - mid;  // 左数组  int[] leftArr = new int[leftLen];  // 右数组  int[] rightArr = new int[rightLen];  // 装载左边数组，（已排序合并完成）  for (int i = 0; i < leftLen; ++i)
            leftArr[i] = arr[left + i];  // 装载右边数组，（已排序合并完成）  for (int j = 0; j < rightLen; ++j)
            rightArr[j] = arr[mid + 1 + j];  // 进行最小值比较并合并到 arr 指定位置  int i = 0, j = 0, k = left;  while (i < leftLen && j < rightLen) { if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];  i++;  } else {
                arr[k] = rightArr[j];  j++;  }
            k++;  } // 比较合并完成，左边数组有剩余，剩余部分填充到 arr  while (i < leftLen) {
            arr[k] = leftArr[i];  i++;  k++;  } // 比较合并完成，右边数组有剩余，剩余部分填充到 arr  while (j < rightLen) {
            arr[k] = rightArr[j];  j++;  k++;  }
    }
}