排序--归并排序

原理：
1、算法基本思路
    　设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。

（1）合并过程
    　合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[p]中，然后将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。
    　重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子文件中剩余记录依次复制到R1中即可。

（2）动态申请R1
    　实现时，R1是动态申请的，因为申请的空间可能很大，故须加入申请空间是否成功的处理。
实现：

 //将分组a[low]..a[i]和分组a[i + 1]..a[high]合并 
 private static void merge(int[] a, int pivotPos, int low, int high)
 {
  int[] b = new int[a.length];
  int p = low;
  int q = pivotPos + 1;
  int r = low;
  while( p <= pivotPos && q <= high )
  {
   while( p <= pivotPos )
   {
    if( a[p] <= a[q] )
     b[r++] = a[p++];
    else
     break;
   }
   while( q <= high )
   {
    if( a[q] < a[p] )
     b[r++] = a[q++];
    else
     break;
   }
  }
  while( p <= pivotPos )
   b[r++] = a[p++];
  while( q <= high )
   b[r++] = a[q++];

  for( int i = low; i <= high; i++)
   a[i] = b[i];
 }
 
 //归并排序
 //分治策略
 //实践复杂度无论最好、平均都为O(nlogn)
 //空间复杂度：O(n),一个额外的数组
 public static void mergeSort(int[] a, int low, int high)
 {
  if ( low >= high )
   return;
  int pivotPos = (low + high) / 2;
  mergeSort(a, low, pivotPos);
  mergeSort(a, pivotPos + 1, high);
  merge(a, pivotPos, low, high);
 }

复杂度：
最好，最坏，平均都为O(nlogn)

空间复杂度： O(n)，因为使用了一个额外的数组

稳定性：归并排序是稳定排序