归并排序（MergeSort）

算法思路：

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[] {2, 4, 5, 8, 1, 2, 3, 6};
        mergeSort(arr, 0, arr.length - 1);
        for(int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
          
    }
      
    public static void mergeSort(int[] A, int p, int r) {
          
        if(p < r) {
            int q = (int) Math.floor((r + p) / 2);
            mergeSort(A, p, q);
            mergeSort(A, q + 1, r);
            merge(A, p, q, r);
        }
    }
      
    //归并
    public static void merge(int[] A, int p, int q, int r) {
//      int[] L = new int[q - p + 1]; //左边的序列
//      int[] R = new int[r - q]; //右边的序列
        int[] L = new int[q - p + 1 + 1]; //左边的序列+哨兵
        int[] R = new int[r - q + 1]; //右边的序列 + 哨兵
          
        //给左右边的序列赋值
        for(int i = 0; i< L.length - 1; i++) {
            L[i] = A[p + i];
        }
        L[L.length - 1] = 65535; //左边序列的哨兵元素
        for(int i = 0; i < R.length - 1; i++) {
            R[i] = A[q+1+i];
        }
        R[R.length - 1] = 65535; //右边序列的哨兵元素
          
        int l_index = 0;
        int r_index = 0;
          
        for(int k = p; k <= r; k ++) { //设置A的索引
              
            if(L[l_index] <= R[r_index]) {
                A[k] = L[l_index];
                l_index ++; //引用后移
            } else {
                A[k] = R[r_index];
                r_index ++; //引用后移
            }
        }
          
    }
}

归并排序（MergeSort）,布布扣,bubuko.com

归并排序（MergeSort）

原文：http://chenjizhan.blog.51cto.com/2577729/1395572