学步园

         归并算法将两个有序的数组合并到一个数组中并使之有序，这两个数组并不一定相同大小，但需要一个额外的数组存放归并结果。算法比较两个数组相同位置的元素，将小的放入结果数组中，如此往复，如果其中一个先到达末尾，则将另外一个剩下部分放入结果数组中。

   归并排序将数组不断划分, 第一次分成两半, 第二次分成四份, 如此直到得到只有一个元素的数组返回, 假定一个元素是有序的, 然后将两个数据项归并到两个元素的有序数组中, 再次返回, 将这一对两个元素的数组归并到一个四个元素的数组中, 返回最外层的时候, 这个数组将会有两个分别有序的子数组, 再次归并则完成排序.

下面是合并两个数组的代码，其实是归并排序的一部分。

 ////////////////// merge sort ///////////////

// lowPtr: 第一个数组的起始索引，

//highPtr: 第二个数组的起始索引.

//upperBound: 第二个数组的最大索引.
 private void merge (int lowPtr, int highPtr, int upperBound) {
  int idx = 0;          //结果数组的索引初始为0
  int lowerBound = lowPtr;  //保存第一个数组的起始点
  int middle = highPtr - 1;   //第一个数组的最大索引. 因为要归并的两个数组相邻.
  

  // 只要有一个数组到达末尾就结束
  while (lowPtr <= middle && highPtr <= upperBound) {
   if ( array[lowPtr] < array[highPtr] ) { //哪个小就放进结果数组
    workspace[idx++] = array [lowPtr++];
   }
   else{
    workspace[idx++] = array [highPtr++];
   }
  }

  while (lowPtr <= middle) {  //第二个数组先结束了
   workspace[idx++] = array[lowPtr++];
  }
  while (highPtr <= upperBound ) { //第一个数组先结束了

   workspace[idx++] = array[highPtr++];
  }

 //将结果数组里的归并后元素拷回原数组

  for ( int i = 0; i

     array [lowerBound+i] = workspace [i];
  }
 }

划分数组则简单地用递归的方法,下面是排序的方法.

//lowerBound: 待排序数组的起始索引

//upperBound: 待排序数组的结束索引

 private void sort (int lowerBound, int upperBound) {
  if (lowerBound == upperBound) { //如果只有一个元素了就返回
   return;
  }
  else {
   int mid = (lowerBound + upperBound) / 2; //找到中间位置

   sort (lowerBound, mid); //排左边
   sort (mid+1, upperBound); //排右边

   merge (lowerBound, mid+1, upperBound); //归并
  }
 }

      对于N个元素的数组来说, 如此划分需要的层数是以2为底N的对数, 每一层中, 每一个元素都要复制到结果数组中, 并复制回来, 所以复制2N次, 那么对于归并排序,它的时间复杂度为O(N*logN), 而比较次数会少得多, 最少需要N/2次,最多为N-1次, 所以平均比较次数在两者之间. 它的主要问题还是在于在内存中需要双倍的空间.