递归关系

“递归”一词字面意思是再次发生。

归并排序

归并排序是递归算法的一个典型教科书示例。其思想非常简单：我们将数组分成两个相等的部分，递归地对它们进行排序，然后将两个已排序的数组合并。递归的终止条件是当数组大小缩小到只有一个元素时。单个元素的数组本身就是有序的。

我们将通过展开算法中所有的递归调用来分析归并排序的时间复杂度，并考察每一层递归的开销。总开销等于每一层开销的总和。

递归解法的运行时间通常用一个递推方程来表示（即一个用函数在更小输入规模上的值来描述该函数本身的方程或不等式）。递归算法的运行时间就是这个递推方程的解。递归算法的递推方程通常具有如下形式：

运行时间 = 划分为 n 个子问题的代价 + n × 求解每个子问题的代价 + 合并所有 n 个问题的代价

对于归并排序而言，我们把原数组划分为两个大小相等的子数组，也就是将原始问题分解为需要递归求解的子问题。

以下是归并排序的递推方程：

运行时间 = 划分为两个未排序数组的代价 + 2 × 排序原数组一半的代价 + 合并两个已排序数组的代价

$T(n) = 划分为两个未排序数组的代价 + 2* T(\frac{n}{2}) + 合并两个已排序数组的代价 \:当 \:n > 1$ $T(n) = O(1) \:\:当\: n = 1$

请注意，该递推方程的解就是算法在规模为 n 的输入上的运行时间。

归并排序的递归树

[归并排序的工作过程]

归并排序的实现

1class Demonstration {
2  
3  private static int[] scratch = new int[10];
4  
5  public static void main( String args[] ) {
6    int[] input = new int[]{ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
7    printArray(input,"Before: ");
8    mergeSort(0, input.length-1, input);
9    printArray(input,"After:  ");
10    
11  }
12  
13  private static void mergeSort(int start, int end, int[] input) {
14
15    if (start == end) {
16      return;
17    }
18
19    int mid = (start + end) / 2;
20
21    // 排序前半部分
22    mergeSort(start, mid, input);
23
24    // 排序后半部分
25    mergeSort(mid + 1, end, input);
26
27    // 合并两个已排序的数组
28    int i = start;
29    int j = mid + 1;
30    int k;
31
32    for (k = start; k <= end; k++) {
33      scratch[k] = input[k];
34    }
35
36    k = start;
37    while (k <= end) {
38
39      if (i <= mid && j <= end) {
40        input[k] = Math.min(scratch[i], scratch[j]);
41
42        if (input[k] == scratch[i]) {
43          i++;
44        } else {
45          j++;
46        }
47      } else if (i <= mid && j > end) {
48        input[k] = scratch[i];
49        i++;
50      } else {
51        input[k] = scratch[j];
52        j++;
53      }
54      k++;
55    }
56  }
57  
58  private static void printArray(int[] input, String msg) {
59    System.out.println();
60    System.out.print(msg + " ");
61    for (int i = 0; i < input.length; i++)
62      System.out.print(" " + input[i] + " ");
63    System.out.println();
64  }
65  
66  
67}

分割代价

第19行对应将原问题划分为两个子问题的代价，每个子问题的规模是原数组的一半。这一划分仅涉及简单的数学运算，可在常数时间内完成，因此可认为将问题划分为两个子问题的代价是常数。记作 d。

合并代价

第27至55行对应合并两个已排序数组的代价。注意此处使用了一个临时数组（scratch array）。虽然归并排序可以原地实现，但那样做并不容易。目前我们采用额外数组的方式。可以看到合并部分包含两个循环：

1. 第32到34行的 for 循环
2. 第37到55行的 while 循环

注意：这两个循环的迭代次数均为 end - start + 1，这正是当前算法所处理子问题的规模。合并两个数组的代价随输入规模变化如下：

• 每个数组大小 = $\frac{n}{2}$，合并代价 = 2 × $\frac{n}{2}$ = $n$
• 每个数组大小 = $\frac{n}{4}$，合并代价 = 2 × $\frac{n}{4}$ = $\frac{n}{2}$
• 每个数组大小 = $\frac{n}{8}$，合并代价 = 2 × $\frac{n}{8}$ = $\frac{n}{4}$
• 规模 = 1，代价 = 1 —— 递归的基准情况

求解两个规模减半的子问题的代价

求解两个规模为原数组一半的子问题的代价并不直观，因为每个子问题都通过一次对归并排序的递归调用来表达。

先从基准情况开始：当问题规模缩小到单个元素时，单元素数组天然有序，递归终止。此时求解的代价为常数时间。为简化起见，假设该代价为1。