归并排序

public class Main {  
    private static int[] tempArr;  
    public static void main(String[] args) {  
        int[] arr = new int[]{20, 10, 50, 30, 80, 50, 70, 40};  
        tempArr = new int[arr.length];  
        mergeSort(arr, 0, arr.length - 1);  
        for (int i : arr) {  
            System.out.println(i);  
        }  
    }  
  
    public static void mergeSort(int[] arr, int begin, int end) {  
        if (begin >= end) {  
            return;  
        }  
        int mid = (begin + end) >>> 1;  
        mergeSort(arr, begin, mid);  
        mergeSort(arr, mid + 1, end);  
        mergeArr(arr, begin, mid, end);  
    }  
  
    public static void mergeArr(int[] arr, int begin, int mid, int end) {  
        int leftPos = begin;  
        int rightPos = mid + 1;  
        int tempArrPos = begin;  
          
        while (leftPos <= mid && rightPos <= end) {  
            tempArr[tempArrPos++] = arr[leftPos] <= arr[rightPos] ? arr[leftPos++] : arr[rightPos++];  
        }  
          
        while (leftPos <= mid) {  
            tempArr[tempArrPos++] = arr[leftPos++];  
        }  
        while (rightPos <= end) {  
            tempArr[tempArrPos++] = arr[rightPos++];  
        }  
          
        for (int i = begin; i <= end; i++) {  
            arr[i] = tempArr[i];  
        }  
    }  
}

快速排序