MergeSort：把整个数组分解为单个元素，再向上Merge

Merge：合并两个已经有序的数组为一个有序数组

 

public class P2_3_1 {    public static void main(String[] args) {        int[] A = {3,41,52,26,38,57,9,49};        int p = 0,q = A.length-1;        MergeSort(A,p,q);        for(int i = 0;i < A.length;i++) {            System.out.println(A[i]);        }    }    public static void MergeSort(int[] A,int p,int q){            if(p < q) {                int r = (p+q)/2;                MergeSort(A,p,r);                MergeSort(A,r+1,q);                Merge(A,p,r,q);            }            }    public static void Merge(int[] A,int p,int r,int q) {        int n1 = r-p+1;        int n2 = q-r;        int[] L = new int[n1+1];        int[] R = new int[n2+1];        for(int i = 0;i < n1;i++) {            L[i] = A[p+i];        }        for(int j = 0;j < n2;j++) {            R[j] = A[r+1+j];        }        L[n1] = 999;    //999表示无穷大，作为哨兵        R[n2] = 999;        int i = 0,j = 0;        for(int k = p;k < q+1;k++) {            if(L[i] < R[j]) {                A[k] = L[i];                i = i+1;            }else {                A[k] = R[j];                j = j+1;            }        }        }}