深入理解归并排序（Merge Sort）

归并排序

伪代码

效率分析

• 归并排序首先将 list 划分为两部分，因此可以保证均匀切分。
• 递归调用后，合并两个子序列需要线性时间的工作量。
• 基本思想：
  • 为两个子序列分别维护一个索引指针。
  • 复制较小的元素，并向前移动对应的指针。
  • 重复此过程，直到其中一个序列为空，然后直接复制另一个序列中剩余的所有元素。
• 合并过程需要使用一个大小为 $O(n)$ 的临时数组。
• 递推关系式：$$C(n)=2C\left(\frac{n}{2}\right)+n$$
• 根据主定理（Master Theorem），时间复杂度为 $O(n \log n)$。
• 实际上，这是一个性能保证（最好、最坏和平均时间复杂度都是 $O(n \log n)$）。

代码示例

Code Sample 18: Java Merge Sort for integers

public static void mergeSort (int a [] , int low , int high )
{
  if ( low < high ) {
    int middle = ( low + high ) / 2;
    // 修正原文笔误：将 mergesort 修改为 mergeSort
    mergeSort ( a, low , middle ) ;
    mergeSort ( a, middle + 1 , high ) ;
    merge ( a, low , middle , high ) ;
  }
}

Code Sample 19: Java Merge for integers

private static int MERGE_HELPER [];
...

private static void merge (int a [] , int low , int middle , int high )
{
  // Copy both parts into the helper array
  for (int i = low ; i <= high ; i ++) {
    MERGE_HELPER [ i ] = a [ i ];
  }
  int i = low ;
  int j = middle + 1;
  int k = low ;
  // Copy the smallest values from the left or the right side back to the original array
  while ( i <= middle && j <= high ) {
    if ( MERGE_HELPER [ i ] <= MERGE_HELPER [ j ]) {
      a [ k ] = MERGE_HELPER [ i ];
      i ++;
    } else {
      a [ k ] = MERGE_HELPER [ j ];
      j ++;
    }
    k ++;
  }
  // Copy the rest of the left side of the array into the target array
  while ( i <= middle ) {
    a [ k ] = MERGE_HELPER [ i ];
    k ++;
    i ++;
  }
  // Copy the rest of the right side of the array into the target array
  while ( j <= high ) {
    a [ k ] = MERGE_HELPER [ j ];
    k ++;
    j ++;
  }
}

Code Sample 20: C Merge Sort for integers

void mergeSort (int * array , int left , int right )
{
  int mid = ( left + right ) /2;
  /* We have to sort only when left < right because when left = right it is anyhow sorted */
  if( left < right )
  {
  /* Sort the left part */
  mergeSort ( array , left , mid ) ;
  /* Sort the right part */
  // 修正原文笔误：将 mid +, right 修改为 mid + 1, right
  mergeSort ( array , mid + 1, right ) ;
  /* Merge the two sorted parts */
  merge ( array , left , mid , right ) ;
  }
}