Javaデータ構造（一）---並べ替え（三）並べ替え

一、並べ替え
は、分割の思想1、ステップサイズ（gap）2、ステップサイズによってデータ（固定長データ＋残データ）3、小領域で並べ替えられます。

   public int[] mergeSort(int[] A, int n) {
     for (int gap = 1; gap < A.length; gap = 2 * gap) 
        MergePass(A, gap, n);
     return A;
    }


    public void MergePass(int[] A, int gap, int length) {

        int i = 0;
    //   gap         
        for (i = 0; i + 2 * gap < length; i += 2 * gap) {
               Merge(A, i, i + gap - 1, i + 2 * gap - 1);
       }
    //       ，      gap
        if (i + gap  < length) {
            Merge(A, i, i + gap - 1, length-1);
       }

     }

    /**
      ，          ，        

    */
    public void Merge(int[] A, int low,int mid,int high){
        int i=low;
        int j=mid+1;
        int k=0;
        int[] A2=new int[high-low+1];
        while(i<=mid && j<=high){
            if(A[i]<=A[j]){
                A2[k]=A[i];
                k++;
                i++;
            }else{
                A2[k]=A[j];
                k++;
                j++;
            }
        }

        while(i<=mid){
            A2[k]=A[i];
            k++;
            i++;
        }

        while(j<=high){
            A2[k]=A[j];
            k++;
            j++;
        }

        for(k=0,i=low;i<=high;i++,k++){
            A[i]=A2[k];
        }
    }