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

合并排序（Merge Sort）是一种分治策略的经典排序算法，它将一个大数组分成两个较小的部分，递归地对这两个部分进行排序，然后将它们合并成一个有序的整体。以下是一个简单的C++实现：

#include <iostream>
#include <vector>
#include <ctime>

// 合并两个已排序的子序列
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++];
        }
    }

    // 将剩余未复制的数据添加到临时数组
    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);
    }
}

// 主程序
int main() {
    srand(time(0)); // 设置随机数种子
    const int data_size = 1e6; // 用于演示，你可以替换为所需的数值

    std::vector<int> nums(data_size); // 生成随机整数
    for (auto& num : nums) {
        num = rand() % data_size; // 生成0到data_size-1之间的随机整数
    }

    auto start_time = std::chrono::high_resolution_clock::now(); // 记录开始时间
    mergeSort(nums, 0, nums.size() - 1);
    auto end_time = std::chrono::high_resolution_clock::now(); // 记录结束时间

    double time_taken = std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time).count() * 1e-6; // 时间计算（单位：秒）

    // 输出时间消耗
    std::cout << "Time taken to sort " << nums.size() << " elements: " << time_taken << " seconds\n";

    // 如果你想展示一个100个数据的排序结果，可以单独调用：
    std::vector<int> small_data(100);
    for (int i = 0; i < 100; ++i) {
        small_data[i] = rand() % 100;
    }
    mergeSort(small_data, 0, small_data.size() - 1);

    // ...此处输出small_data的排序结果...

    return 0;
}

为了获得不同规模数据的排序时间，你需要分别更改`nums`中的大小，如`data_size = 100000`, `1000000`, `50000000`, 和 `10000000`。记住，实际运行时可能因系统性能差异导致时间略有不同。

执行这个程序后，你会得到类似这样的信息：

Time taken to sort 1000000 elements: 0.057385 seconds
Time taken to sort 10000000 elements: 0.492345 seconds
Time taken to sort 50000000 elements: 2.46123 seconds
Time taken to sort 100000000 elements: 5.10987 seconds

以及100个数据的排序结果。