2019-07-31 归并排序

public class MergeSort {

    public static void main(String[] args) {
        int[] a = {2,51,3,8,5,16,9};
        mergeSort(a,0,a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    private static void mergeSort(int[] a, int left, int right) {
        // 递归终止条件
        if(left>=right){
            return;
        }

        int middle = left + (right -left)/2;
        mergeSort(a,left,middle);
        mergeSort(a,middle+1,right);
        merge(a,left,middle,right);
    }

    private static void merge(int[] a, int left, int middle, int right) {
        // 使用临时数组存储结果
        int p = left;
        int q = middle + 1;
        int k = 0;

        int[] temp = new int[right-left+1];
        while(p<=middle && q<=right){
            if(a[p]<a[q]){
                temp[k++] = a[p++];
            }else{
                temp[k++] = a[q++];
            }
        }

        while(p<=middle){
            temp[k++] = a[p++];
        }
        while (q<=right){
            temp[k++] = a[q++];
        }

        for(int i = 0; i<=right-left;i++){
            a[left+i] = temp[i];
        }

    }
}