归并排序 java实现

排序思路：

先分组，分成一个个小的数组，然后再组合，组合的过程中排序，整个归并的过程中使用递归

    //分+归并
    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if (left < right){
            int mid = (left + right) / 2;
            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid+1,right,temp);
            merge(arr,left,right,mid,temp);
        }
    }


    //排序
    public static void merge(int[] arr,int left,int right,int mid,int temp[]){
        int l = left;
        int r = mid + 1;
        int t = 0;
        while (l <= mid && r <= right){
            if (arr[l] <= arr[r]){
                temp[t] = arr[l];
                l++;
                t++;
            } else {
                temp[t] = arr[r];
                r++;
                t++;
            }
        }

        while (l <= mid){
            temp[t] = arr[l];
            t++;
            l++;
        }
        while (r <= right){
            temp[t] = arr[r];
            r++;
            t++;
        }

        //3.放回arr数组
        t = 0;
        int leftTemp = left;
        while (leftTemp <= right){
            arr[leftTemp] = temp[t];
            t++;
            leftTemp++;
        }
    }