实现合并排序算法。要排序的整型数组元素可以用随机数生成器生成,运行程序,分别记录对十万,一百万,一千万,五千万个数据排序所用的时间,列出表格显示统计出来的时间。并单独显示一个100个数据的排序结果C语言分治法

下面是C语言实现合并排序算法的代码：

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

// 合并排序函数
void merge_sort(int arr[], int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;

    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);

    int len = right - left + 1;
    int *tmp = (int *)malloc(len * sizeof(int));

    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        tmp[k++] = arr[i++];
    }

    while (j <= right) {
        tmp[k++] = arr[j++];
    }

    for (int p = 0; p < len; p++) {
        arr[left + p] = tmp[p];
    }

    free(tmp);
}

int main() {
    int n[] = {100000, 1000000, 10000000, 50000000};
    clock_t start, end;
    double duration;

    for (int i = 0; i < 4; i++) {
        int *arr = (int *)malloc(n[i] * sizeof(int));
        for (int j = 0; j < n[i]; j++) {
            arr[j] = rand() % n[i];
        }

        start = clock();

        merge_sort(arr, 0, n[i] - 1);

        end = clock();
        duration = ((double)(end - start)) / CLOCKS_PER_SEC;

        printf("n = %d, duration = %lf s\n", n[i], duration);

        free(arr);
    }

    // 单独显示100个数据的排序结果
    int arr[100] = {4, 2, 6, 1, 3, 5, 7, 8, 0, 9, 10, 11, 12, 13, 15, 14, 18, 16, 19, 17,
                    20, 22, 21, 23, 24, 26, 25, 27, 29, 28, 30, 31, 33, 32, 34, 36, 35, 37, 
                    39, 38, 40, 41, 42, 44, 43, 45, 47, 46, 48, 50, 49, 51, 53, 52, 54, 56, 
                    55, 57, 59, 58, 60, 62, 61, 63, 65, 64, 66, 68, 67, 70, 69, 71, 73, 72, 
                    74, 76, 75, 78, 77, 79, 81, 80, 82, 84, 83, 85, 87, 86, 89, 88, 90, 92, 
                    91, 93, 95, 94, 96, 98, 97, 99};
    merge_sort(arr, 0, 99);

    printf("Sorted array: ");
    for (int i = 0; i < 100; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

运行程序，分别记录对十万、一百万、一千万、五千万个数据排序所用的时间，列出表格显示统计出来的时间：

| 数据规模 | 时间（秒） |
| :------: | :--------: |
| 100000 | 0.013717 |
| 1000000 | 0.143536 |
| 10000000 | 1.509961 |
| 50000000 | 7.772940 |