实现合并排序算法。要排序的整型数组元素可以用随机数生成器生成，运行程序，分别记录对十万，一百万，五千万，一千万个数据排序所用的时间，列出表格显示统计出来的时间。并单独显示一个100个数据的排序结果。用C++编写，完整且正确的输出代码，写上完整的注释

#include <iostream>
#include <vector>
#include <chrono> // 需要用到高精度时间测量
#include <random> // 随机数生成器

// 合并排序函数，使用分治策略
template<typename T>
void mergeSort(T 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);
    }
}

// 合并函数，将两个已排序区间合并回原数组
template<typename T>
void merge(T arr[], int left, int mid, int right) {
    int leftSize = mid - left + 1;
    int rightSize = right - mid;

    T* leftArr = new T[leftSize]; // 左半部分临时数组
    T* rightArr = new T[rightSize]; // 右半部分临时数组

    // 将左、右两边的元素复制到临时数组
    for (int i = 0; i < leftSize; ++i)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < rightSize; ++j)
        rightArr[j] = arr[mid + 1 + j];

    // 按顺序将较小元素放入原数组
    int i = 0, j = 0, k = left;
    while (i < leftSize && j < rightSize) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }

    // 如果有剩余元素，则直接复制未遍历完的那一边
    while (i < leftSize)
        arr[k++] = leftArr[i++]; // 左边剩余
    while (j < rightSize)
        arr[k++] = rightArr[j++]; // 右边剩余

    // 释放临时数组
    delete[] leftArr;
    delete[] rightArr;
}

// 生成随机数组
std::vector<int> generateRandomArray(int size, std::default_random_engine& generator) {
    std::uniform_int_distribution<int> distribution(0, 10000); // 0-10000范围内的随机数
    std::vector<int> arr(size);
    for (int& num : arr)
        num = distribution(generator);
    return arr;
}

// 记录和打印排序时间
void measureAndPrint(const std::string& title, const std::vector<int>& data) {
    auto start = std::chrono::high_resolution_clock::now();
    mergeSort(data.data(), 0, data.size() - 1);
    auto end = std::chrono::high_resolution_clock::now();
    double time_used = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() * 1e-6; // 微秒转换为秒

    std::cout << "Sorted " << title << ": Time taken: " << time_used << " seconds\n";
    std::cout << "Sorted array: ";
    for (const auto& num : data) {
        std::cout << num << ' ';
    }
    std::cout << "\n";
}

int main() {
    std::random_device rd;
    std::mt19937 gen(rd()); // 使用Mersenne Twister随机数生成器
    std::uniform_int_distribution<> distr(0, 100000000); // 0-1亿范围内的随机数

    // 不同规模的数据排序时间测量
    const int sizes[] = {100000, 1000000, 5000000, 10000000};
    std::vector<int> arr[4]; // 用于存储不同大小的数组
    for (size_t i = 0; i < sizeof(sizes) / sizeof(sizes[0]); ++i) {
        arr[i] = generateRandomArray(sizes[i], gen);
        measureAndPrint("Data with " + std::to_string(sizes[i]) + " elements", arr[i]);
    }

    // 单独显示100个数据的排序结果
    std::vector<int> smallArr(100);
    for (auto& num : smallArr)
        num = distr(gen);
    measureAndPrint("Small Data with 100 elements", smallArr);

    return 0;
}

这段代码首先定义了一个`mergeSort`函数用于执行归并排序，然后创建了一个`generateRandomArray`函数用于生成指定长度的随机整数数组。`measureAndPrint`函数负责记录排序时间和打印结果。在`main`函数中，我们生成了不同数量级的数据（10万、100万、500万和1000万）并计算排序所需时间。