√n段合并排序算法： 将数组 划分为 √n个子数组，每个子数组有 个元素。然后递归地对分割后的子数组进行排序，最后将所得到的 个排好序的子数组合并排序。写出上述问题的c++解题代码并分析其时间复杂度

√n段合并排序（也称为二分归并排序的一种变体），通常适用于大规模数据集，尤其是当内存不足以一次性存储整个数组时。它的基本思想是将数组分成大小约为√n的若干部分，分别排序，然后逐层合并。这个过程可以用递归的方式来实现。

下面是一个简单的C++代码示例：

#include <vector>
#include <algorithm>

void merge(std::vector<int>& arr, int start, int mid, int end) {
    std::vector<int> temp(end - start + 1);
    int i = start, j = mid + 1, k = 0;

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

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

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

    for (i = start; i <= end; i++) {
        arr[i] = temp[i - start];
    }
}

void sqrtMergeSort(std::vector<int>& arr, int n) {
    if (n <= 1) return;
    int size = static_cast<int>(std::sqrt(n));
    for (int i = 0; i * size < n; i += size) {
        merge(arr, i, i + size - 1, min(i + size * 2 - 1, n - 1));
    }
    sqrtMergeSort(arr, size); // 对剩下的小数组递归排序
}

// 示例：
int main() {
    std::vector<int> vec = {9, 7, 5, 11, 12, 2, 14, 3, 10};
    int n = vec.size();
    sqrtMergeSort(vec, n);
    for (const auto& num : vec) {
        std::cout << num << " ";
    }
    return 0;
}

时间复杂度分析：
- 归并操作的时间复杂度为O(m)，其中m为子数组长度，因为需要遍历一次临时数组。
- 当数组大小为√n时，会执行一次合并操作。
- 对于规模为√n的小数组，递归深度为log(√n) ≈ log(n^(1/2)) ≈ O(log n)次。
- 所以总的时间复杂度是所有子数组的合并操作次数乘以合并操作的时间复杂度，即O(n * log n)。这是因为每次递归都会把问题规模减半，所以总的操作数是n。