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

在C++中实现归并排序算法，你可以按照以下步骤操作：

#include <iostream>
#include <vector>
#include <chrono>

// 合并函数，将两个已排序的部分合并成一个有序数组
void merge(std::vector<int>& arr, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 将剩余部分复制到temp
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

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

    // 把临时数组的内容复制回原数组
    for (int x = 0; x < temp.size(); ++x) {
        arr[left + x] = temp[x];
    }
}

// 归并排序主函数
void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);   // 分治法左半部分
        mergeSort(arr, mid + 1, right); // 分治法右半部分
        merge(arr, left, mid, right);  // 合并两部分
    }
}

// 测试和计时函数
void measureTime(const std::vector<int>& data, int size, std::string name) {
    auto start = std::chrono::high_resolution_clock::now();
    mergeSort(data, 0, size - 1);
    auto end = std::chrono::high_resolution_clock::now();

    double time_spent = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() / 1e6;
    std::cout << "对于" << name << "个数据，排序时间是：" << time_spent << "秒\n";
}

int main() {
    const int N = 100; // 示例排序规模
    std::vector<int> smallData(N, 0); // 创建一个包含100个随机数的向量

    // 使用随机数填充示例数据
    for (int& num : smallData) {
        num = rand() % 100;  // 在0-99之间取随机数
    }

    measureTime(smallData, N, "100个");

    // 对于大规模数据，你需要创建更大规模的数据，并循环调用measureTime，比如这样：
    // std::vector<int> largeData(10000000, 0); // 10M数据
    // measureTime(largeData, 10000000, "1M百万");
    // measureTime(largeData, 50000000, "5M五百万");
    // measureTime(largeData, 100000000, "10M一千万");

    return 0;
}

这个例子展示了如何实现归并排序以及对小规模数据的排序计时。为了获取百万、千万级别的排序时间，你需要创建更大的数据集，并重复测量排序过程。