归并排序

递归

    public static void mergeSort(int[] data){
        int[] tmpArr = new int[data.length];
        mergeSort(data,tmpArr,0,data.length-1);
    }
    
    public static void mergeSort(int[] data,int[] tmpArr, int left, int right) {  
        if(left < right){
            int mid = (left + right) / 2;
            mergeSort(data,tmpArr,left,mid);
            mergeSort(data,tmpArr,mid+1,right);
            merge(data,tmpArr,left,mid+1,right);
        }
    }  
  
    public static void merge(int[] data,int[] tmpArr,int leftPos,int rightPos,int rightEnd){
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int count = rightEnd - leftPos + 1;
        while (leftPos <= leftEnd && rightPos <= rightEnd){
            if(data[leftPos] < data[rightPos]){
                tmpArr[tmpPos++] = data[leftPos++];
            }else{
                tmpArr[tmpPos++] = data[rightPos++];
            }
        } 
        while(leftPos <= leftEnd){
            tmpArr[tmpPos++] = data[leftPos++];
        }
        while (rightPos <= rightEnd){
            tmpArr[tmpPos++] = data[rightPos++];
        } 
        for(int i = 0; i < count; i++){
            data[rightEnd] = tmpArr[rightEnd];
            rightEnd--;
        }
    }