使用原地归并排序算法和在小规模数据时采用插入排序算法的归并排序算法的C语言实现代码

以下是原地归并排序算法和在小规模数据时采用插入排序算法的归并排序算法的C语言实现代码：

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

#define MIN_SIZE 10

void merge(int *arr, int *tempArr, int leftPos, int rightPos, int rightEnd)
{
    int leftEnd = rightPos - 1;
    int tempPos = leftPos;
    int numElements = rightEnd - leftPos + 1;

    while (leftPos <= leftEnd && rightPos <= rightEnd)
    {
        if (arr[leftPos] <= arr[rightPos])
            tempArr[tempPos++] = arr[leftPos++];
        else
            tempArr[tempPos++] = arr[rightPos++];
    }

    while (leftPos <= leftEnd)
        tempArr[tempPos++] = arr[leftPos++];

    while (rightPos <= rightEnd)
        tempArr[tempPos++] = arr[rightPos++];

    for (int i = 0; i < numElements; ++i, --rightEnd)
        arr[rightEnd] = tempArr[rightEnd];
}

void mSort(int *arr, int *tempArr, int left, int right)
{
    if (left < right)
    {
        int center = (left + right) / 2;

        mSort(arr, tempArr, left, center);
        mSort(arr, tempArr, center + 1, right);

        if (arr[center] > arr[center + 1])
            merge(arr, tempArr, left, center + 1, right);
    }
}

void mergeSort(int *arr, int n)
{
    int *tempArr = malloc(n * sizeof(int));
    if (tempArr != NULL)
    {
        mSort(arr, tempArr, 0, n - 1);
        free(tempArr);
    }
    else
    {
        printf("Error: Out of memory\n");
        exit(1);
    }
}

void insertionSort(int *arr, int n)
{
    for (int i = 1; i < n; ++i)
    {
        int j = i;
        int tmp = arr[i];

        while (j > 0 && tmp < arr[j - 1])
        {
            arr[j] = arr[j - 1];
            --j;
        }

        arr[j] = tmp;
    }
}

void hybridMergeSort(int *arr, int n)
{
    int *tempArr = malloc(n * sizeof(int));
    if (tempArr != NULL)
    {
        if (n > MIN_SIZE)
            mSort(arr, tempArr, 0, n - 1);
        else
            insertionSort(arr, n);

        free(tempArr);
    }
    else
    {
        printf("Error: Out of memory\n");
        exit(1);
    }
}

int main()
{
    int arr[] = { 5, 9, 1, 4, 8, 3, 7, 6, 2 };
    int n = sizeof(arr) / sizeof(int);

    printf("Before sorting:\n");
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);

    hybridMergeSort(arr, n);

    printf("\nAfter sorting:\n");
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);

    return 0;
}

在上面的代码中，`MIN_SIZE` 定义了插入排序算法的最小规模。如果归并排序的规模小于 `MIN_SIZE`，则使用插入排序算法。在 `hybridMergeSort` 函数中，我们首先分配临时数组 `tempArr`，然后根据数组规模判断使用原地归并排序算法还是插入排序算法。最后，释放临时数组 `tempArr` 的内存。