c语言用递归算法解决归并排序问题

在C语言中，归并排序是一种使用递归算法的经典分治法解决问题的例子。它将数组分为两半，对每一半分别进行排序，然后合并已排序的部分。以下是递归版归并排序的基本步骤：

1. **分解** (Divide): 将待排序数组`arr[]`分成两个长度相等的子数组`left[]` 和 `right[]`。

2. **递归** (Recursion): 对这两个子数组分别调用归并排序函数，直到每个子数组只有一个元素（这是递归的基础情况，因为单个元素已经默认排序）。

3. **合并** (Combine): 当子数组只剩下一个元素时，开始合并过程。创建一个新的临时数组`temp[]`，比较左右子数组的第一个元素，将较小的一个放入`temp[]`，并将对应的数组向后移动一位。重复这个过程，直到所有的元素都被添加到`temp[]`中。

4. **回溯** (Backtrack): 把合并后的有序序列复制回原始数组`arr[]`。

以下是C语言实现归并排序的一个简单示例：

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];

    // 把左边和右边的元素复制到临时数组
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    // 合并临时数组回原数组
    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++;
    }
}

// 归并排序函数
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);
    }
}