归并排序的递归算法是把n元素序列分为2个元序列，使用归并递归地排序2个子序列，再合并2个已经排序的子序列，产生n元素的有序序列。 设归并排序的当前区间是R[low..high]，分治法的三个步骤是: ① 分解：将当前区间一分为二，即求分裂点 ② 求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序； ③ 组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。 递归的终结条件：子区间长度为1。 编程要求 根据提示，在右侧编辑器 Begin-End 区间补充代码，完成函数的定义，实现归并排序的递归算法，具体要求如下： 函数Merge(int a[],int s,int m, int e)实现数组a的局部a[s,m]和a[m+1,e]的归并； 函数MergeSort(int a[],int s,int e)实现数组a[s,e]的归并排序。

#include <iostream>
using namespace std;

void Merge(int a[], int s, int m, int e){
    int i = s, j = m + 1, k = 0;
    int *tmp = new int[e - s + 1];
    while (i <= m && j <= e) {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }
    while (i <= m)
        tmp[k++] = a[i++];
    while (j <= e)
        tmp[k++] = a[j++];
    for (int l = 0; l < k; l++)
        a[s + l] = tmp[l];
    delete[] tmp;
}

void MergeSort(int a[], int s, int e){
    if (s < e) {
        int m = (s + e) / 2;
        MergeSort(a, s, m);
        MergeSort(a, m + 1, e);
        Merge(a, s, m, e);
    }
}

int main() {
    int a[] = {9, 6, 7, 3, 5, 8, 4, 2, 1};
    MergeSort(a, 0, 8);
    for (int i = 0; i < 9; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}