c语言实现归并排序mergesort和merge函数

归并排序 (Mergesort) 是一种分治算法，它将待排序数组分成两半，分别对每一半进行排序，然后合并两个已排序的部分。在 C 语言中，实现归并排序主要包括 `mergesort` 函数和辅助的 `merge` 函数。

`mergesort` 函数通常包含以下步骤：
1. **划分**：如果数组长度大于1，则将其一分为二。
2. **递归**：对左右两个子数组分别进行递归调用 `mergesort`。
3. **合并**：当所有元素都被排序后，通过 `merge` 函数将这两个有序数组合并成一个整体。

`merge` 函数负责合并两个已经排好序的子数组，它的工作原理是：
1. 创建一个新的临时数组用于存放合并后的结果。
2. 分别从两个输入数组的起始位置开始比较元素，选择较小的放入临时数组，并更新对应原数组的位置。
3. 重复上述过程直到有一个数组的所有元素都已经被添加到临时数组。
4. 将另一个数组剩余部分直接复制到临时数组的未填充部分。

以下是简单的 C 代码示例：

#include <stdio.h>
#include <stdlib.h>

// merge function to combine two sorted arrays into one
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // create temporary arrays
    int L[n1], R[n2];

    // copy elements from the first array to temp
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    // copy elements from the second array to temp
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    // merge the temp arrays back into 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++;
    }

    // copy remaining elements of L[] if any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // copy remaining elements of R[] if any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// mergesort function
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);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    mergesort(arr, 0, arr_size - 1);
    printf("Sorted array: \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    return 0;
}