算法设计与分析递归分治代码

### 关于递归分治法的代码实现

#### 归并排序作为递归分治的经典应用案例

归并排序是一种典型的基于递归分治思想设计出来的高效排序算法。该算法通过不断地将数组分割成两半直到不能再分为止，再逐步合并这些被拆分开的小部分从而完成整个序列的有序化处理。

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;

    /* 创建临时数组 */
    int L[n1], R[n2];

    /* 将数据复制到临时数组L[] 和 R[] 中*/
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    /* 合并两个临时数组回到原数组arr[l..r]中 */
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* 复制剩余元素至目标位置 */
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

/* 主函数用于调用merge()来进行实际操作 */
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
         // 找出中间点
         int m = l+(r-l)/2;

         // 对左半边进行排序
         mergeSort(arr, l, m);
         // 对右半边进行排序
         mergeSort(arr, m+1, r);

         // 合并已排序的部分
         merge(arr, l, m, r);
    }
}

上述C++程序展示了如何利用递归分治的思想去编写高效的归并排序算法[^1]。此段代码首先定义了一个辅助函数`merge()`用来执行具体的合并工作；而另一个核心逻辑则由`mergeSort()`负责驱动——它会持续地把待处理区间切分为更小规模的问题实例直至可以直接解决的程度（即单个元素），之后借助之前提到的那个帮助者来组装最终的结果集。

为了提高性能，在某些情况下可以考虑引入缓存机制以减少不必要的重复计算，尤其是在面对那些具有重叠子结构特征的任务时尤为有效[^2]。