归并排序

    private static void mergeSortInternally(int[] arr, int left, int right){

        if (left >= right) return;
  
       //防止和超过int类型最大值
        int mid = left + (right - left)/2;
        mergeSortInternally(arr, left, mid);
        mergeSortInternally(arr, mid+1, right);

        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right){
        int i = left;
        int j = mid + 1;
        int k = 0;
        int[] tmp = new int[right-left+1];// 申请一个大小跟a[p...r]一样的临时数组
        while (i <= mid && j <= right){
            if (arr[i] <= arr[j]){
                tmp[k++] = arr[i++];
            }else {
                tmp[k++] = arr[j++];
            }
        }

        int start = i;
        int end = mid;
        if (j <= right){
            start = j;
            end = right;
        }

        while (start <= end){
            tmp[k++] = arr[start++];
        }

        for (i =0; i <= right - left; ++i){
            arr[left+i] = tmp[i];
        }
    }