c++非递归归并排序

非递归归并排序是一种归并排序的实现方式，它通过迭代而不是递归来实现排序。在非递归归并排序中，将待排序的序列分成若干个长度为1的子序列，然后将相邻的子序列进行归并，得到长度为2的有序子序列，再将相邻的有序子序列进行归并，直到得到一个完整的有序序列。相比递归实现，非递归归并排序的空间复杂度更低，因为它不需要使用递归栈。

下面是c++非递归归并排序的代码实现：

void mergeSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 1; i < n; i *= 2) {
        for (int j = 0; j < n - i; j += 2 * i) {
            int left = j, mid = j + i, right = min(j + 2 * i, n);
            vector<int> temp(right - left);
            int k = 0, p = left, q = mid;
            while (p < mid && q < right) {
                if (nums[p] < nums[q]) {
                    temp[k++] = nums[p++];
                } else {
                    temp[k++] = nums[q++];
                }
            }
            while (p < mid) {
                temp[k++] = nums[p++];
            }
            while (q < right) {
                temp[k++] = nums[q++];
            }
            for (int x = 0; x < k; x++) {
                nums[left + x] = temp[x];
            }
        }
    }
}