算法思想

将两个或两个以上的有序表组合成一个新的有序表，假定待排序列表含有n个记录，则可将其视为n个有序的子表，每个子表的长度为1，然后两两归并，得到新的子表在两两归并……如此重复，知道得到一个长度为n的有序表为止。
归并排序 - 图1 

  1. //归并函数
  2.     public static void merge(int array[], int low, int mid, int high){
  4.         //拷贝数组
  5.         int [] newArray = Arrays.copyOf(array,array.length);
  7.         int i = low, j = mid+1, k = low;
  8.         while ((i <= mid) && (j <= high)){
  9.             if (newArray[i] < newArray[j])
  10.                 array[k++] = newArray[i++];
  11.             else
  12.                 array[k++] = newArray[j++];
  13.         }
  14.         while (i <= mid)
  15.             array[k++] = newArray[i++];
  16.         while (j <= high)
  17.             array[k++] = newArray[j++];
  19.     }
  21.     public static void mergeSort(int array[], int low, int high){
  22.         if (low < high){
  23.             int mid = (low + high) / 2;
  24.             mergeSort(array,low,mid);
  25.             mergeSort(array,mid+1,high);
  26.             merge(array,low,mid,high);
  27.         }
  28.     }

复杂度分析

时间复杂度：每趟归并的时间复杂度为O(n)，共需进行┎log2n┒，所以算法的时间复杂度为O(nlog2n)
空间复杂度：归并操作中，需要n个辅助空间，空间复杂度为O(n)