归并排序（MergeSort）

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

 

下图就是2-路归并排序的一个例子：

 

代价分析：

上图可以看出，一个N关键字的序列，两两归并可以构造一棵高度为[logN]的归并排序树。而每一次归并的时间复杂度为O(m+n)。因此每一趟归并的时间复杂度为O(N)，如上图。归并排序算法的总时间复杂度为O(N*logN) 。其所需要的辅助空间就是一个能容纳中间合并结果的数量为N的连续空间。因此空间复杂度为O(N) 。是稳定排序方法。

 

速度仅次于快速排序。

------------------------------------------------------------------------------------------------

参考资料：

【排序结构4】 归并排序
归并排序
[百度百科]归并排序

-------------------------------------------------------------------------------------------------------------------

我们可以用分治的思想解决归并排序，给定一个有N个关键字的有序序列，分治法的步骤如下：
(1)划分： 如果S中有1个元素，则直接返回S，因为它已经有序了。否则(S中至少有两个元素)，把它们分别放入两个序列S1和S2中，S1和S2各包含大约S中的一半元素，即S1包含S中的前[N/2]个元素，S2包含S中的后[N/2]个元素。
(2)递归：递归求解子问题S1和S2。
(3)求解：归并有序序列S1和S2，使得他们成为一个有序序列，将其中的元素放回S中。

*这里有个问题就是排序的数字序列必须是2的次幂，否则就要处理越出的部分。

-------------------------------------------------------------------------------------------------------------------

public static void MergeSort(int[] array){
      int size = array.length;
      int step=2; // 设定一个步长
      for(; step<=size; step*=2){ // 步长每次以2的指数级增长
            
            for(int i=0; i<size; i+=step){
                  
                  if(i+step<=size){
                        MergeSort(array, i, i+step/2-1, i+step-1);
                  }
                  
            }
      }
      // 对越出的部分(非2的次幂)进行处理
      int lost = size%(step/2);
      if(lost!=0){
            MergeSort(array, 0, size-lost-1, size-1);
      }
}

/**
 * 对有序的子序列进行整合
 * @param array
 * @param start
 * @param mid
 * @param end
 */
private static void MergeSort(int[] array, int start, int mid, int end){
      
      int i=start;
      int j=mid+1;
      int index = 0;
      
      // 分配一个新的空间作为临时储存
      int[] temp = new int[end-start+1];
      // 对有序列进行排序
      while(i<=mid && j<=end){
            temp[index++] = array[i]<array[j]?array[i++]:array[j++];
      }
      while(i<=mid){
            temp[index++] = array[i++];
      }
      while(j<=end){
            temp[index++] = array[j++];
      }
      
      // 数据转移
      index = 0;
      for(int k=start; k<=end; k++){
            array[k] = temp[index++];
      }
      
}