用分治法实现二路归并排序 编写voidmerge(intall.intIow,intmid,inthigh)函数 编写voidmergeSort(intall.intlow,inthigh)函数

二路归并排序是一种采用分治策略的排序算法，它将数组分为两个部分（通常是一个中间点），然后递归地对这两部分进行排序，最后合并这两个有序的部分。这个过程通过`merge`函数完成。

首先，我们来看看如何编写`merge`函数：

void merge(int arr[], int low, int mid, int high) {
    // 创建临时数组temp来存放合并后的结果
    int temp[high - low + 1];
    int i = low; // 左半部分的起始指针
    int j = mid + 1; // 右半部分的起始指针
    int k = 0; // temp数组的指针

    // 比较左右两边的元素并将较小的放入temp数组
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 将剩余未处理的左边元素复制到temp数组
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    // 将剩余未处理的右边元素复制到temp数组
    while (j <= high) {
        temp[k++] = arr[j++];
    }

    // 把temp数组的内容复制回原数组
    for (i = low; i <= high; i++) {
        arr[i] = temp[i - low];
    }
}

接下来是`mergeSort`函数，它是整个排序过程的核心：

void mergeSort(int arr[], int low, int high) {
    if (low < high) {
        // 找到中间点
        int mid = low + (high - low) / 2;

        // 对左半部分和右半部分递归调用mergeSort
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);

        // 一旦两部分排序完成，合并它们
        merge(arr, low, mid, high);
    }
}

这个函数会检查数组的长度是否大于1，如果大于1则会继续拆分，并调用`merge`函数来合并两个已排序的部分。当所有的元素都被排序后，排序结束。