题目1：给定n个数值，从小到大排序。 要求： 1. 输入随机生成0≦x≦10^9数组，长度分别为5、10、100； 2. 采用归并排序输出每次执行的排序结果 3. 时间复杂度、空间复杂度、实际执行时间、实际占用内存空间？ 给出c++代码

题目1的要求是要对一组范围在0到1亿之间的随机整数数组进行排序，并使用归并排序算法完成。以下是C++代码示例：

#include <iostream>
#include <vector>
#include <cstdlib> // 需要用到rand()函数
#include <ctime>   // 设置随机数种子

// 归并排序函数
template<typename T>
void mergeSort(std::vector<T>& arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

// 合并两个已排序区间
template<typename T>
void merge(std::vector<T>& arr, int left, int mid, int right) {
    std::vector<T> 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];
    }
}

int main() {
    srand(time(0)); // 设置随机数种子以获取随机数组
    const int sizes[] = {5, 10, 100}; // 需要排序的数组长度
    for (const auto size : sizes) {
        std::vector<int> arr(size);
        for (int& num : arr) {
            num = rand() % 100000000; // 随机生成0到1亿的整数
        }
        
        std::cout << "排序前: ";
        for (int num : arr) {
            std::cout << num << " ";
        }
        std::cout << "\n";

        mergeSort(arr, 0, arr.size() - 1);
        std::cout << "排序后: ";
        for (int num : arr) {
            std::cout << num << " ";
        }
        std::cout << "\n\n";
    }

    return 0;
}

**性能分析**：
- **时间复杂度**: 归并排序的时间复杂度为O(n log n)，其中n是数组长度。这是因为每一次递归都需要将数组分为两半，然后合并这两半。
- **空间复杂度**: 空间复杂度是O(n)，因为合并过程中需要额外的存储空间来保存待合并的部分。
- **实际执行时间和内存占用**：这会受到硬件、编译器优化以及输入数据的影响，无法提供精确值。在大多数情况下，对于小规模数据，归并排序的实际运行速度较快；对于大规模数据，尤其是由于递归深度导致的栈空间需求，可能会有性能下降。