归并排序算法c++迭代

### C++ 迭代式归并排序算法

迭代式的归并排序可以通过自底向上的方式实现，而不是传统的递归方法。这种方式可以避免递归带来的栈溢出风险，并且同样能够有效地完成排序操作。

下面是一个完整的 C++ 实现：

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left;
    int j = mid + 1;
    int 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 p = 0; p < k; ++p)
        arr[left + p] = temp[p];
}

void iterativeMergeSort(vector<int>& arr) {
    int n = arr.size();
    
    for (int width = 1; width < n; width *= 2) {
        for (int start = 0; start < n; start += 2 * width) {
            int mid = min(start + width - 1, n - 1);
            int end = min(start + 2 * width - 1, n - 1);

            if (mid < end)
                merge(arr, start, mid, end);
        }
    }
}

int main() {
    vector<int> data = {5, 7, 9, 3, 8, 6, 4, 2};
    cout << "Original array:" << endl;
    for (auto& num : data)
        cout << num << ' ';
    cout << endl;

    iterativeMergeSort(data);

    cout << "Sorted array:" << endl;
    for (auto& num : data)
        cout << num << ' ';
    cout << endl;

    return 0;
}

此代码展示了如何使用迭代的方式执行归并排序[^1]。`merge` 函数负责将两个已排序的部分合并成一个新的有序部分；而 `iterativeMergeSort` 则控制整个排序流程，逐步增加待处理序列的长度直到覆盖整个输入数组。