归并排序

归并排序( Merging Sort) 就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n 个记录， 则可以看成是n个有序的子序列，每个子序列的长度为1然后两两归并，得到【n/2】个长度为2或1 的有序子序列; 再两两归并，……，如此重复， 直至得到一个长度为n 的有序序列为止，这种排序方法称为2 路归并排序。

 private static void merged(int[] list, int low, int mid, int high) {
   int i = low;  //第一段序列初始下标
   int j = mid + 1;  //第二段序列初始下标
   //临时存放数组
   int k = 0;
   int[] array = new int[high - low + 1];

   //遍历第一段很第二段序列，直到有一段序列扫描完毕
   //注：这里第一段序列和第二段序列已经是有序数列
   while (i<=mid && j<= high) {
       //将第一段和第二段中，更小的数存放到临时数组中
       if (list[i] <= list[j]) {
           array[k] = list[i];
           i++;
           k++;
       } else {
           array[k] = list[j];
           j++;
           k++;
       }
   }
   //直到其中一段遍历完毕，另一端剩下的数字直接赋值到临时数组中
   while (i <= mid) {
       array[k] = list[i];
       i++;
       k++;
   }

   while (j <= high) {
       array[k] = list[j];
       j++;
       k++;
   }

   //将合并序列复制到原始序列中
   for (k=0, i=low; i<=high; i++, k++ ) {
       list[i] = array[k];
   }
}

private static void mergedPass(int[] list, int gap, int length) {
   int i = 0;
   // 归并gap长度的两个相邻子表
   for (i=0; i+2*gap-1<length; i=i+2*gap) {
       merged( list, i, i+gap-1, i+2*gap-1 );
   }
   // 余下两个子表，后者长度小于gap
   if (i+gap-1 < length) {
       merged( list, i, i+gap-1, length-1 );
   }
}

private static void mergingSort(int[] list) {
   for (int gap=1; gap<list.length; gap=2*gap) {
       mergedPass( list, gap, list.length );
   }
}

public static void main(String[] args) {
    int[] list = {9,1,5,3,4,2,6,8,7};
    mergingSort(list);
    System.out.print( "Merging Sort: ");
    for (int i=0; i<list.length; i++) {
        System.out.print( list[i] + ", " );
    }
}