c++非递归版归并排序

归并排序是一种分治算法，其基本思想是将待排序的数组分为两半，分别对每一部分进行排序，然后合并两个已排序的部分。在非递归版本中，通常使用循环结构和临时数组来避免函数调用带来的额外开销。

以下是C++中非递归归并排序的一个简单实现：

#include <vector>

void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 如果还有剩余元素，直接复制
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void non_recursive_merge_sort(std::vector<int>& arr, int left, int right) {
    if (left >= right)
        return;

    int mid = left + (right - left) / 2;
    non_recursive_merge_sort(arr, left, mid);
    non_recursive_merge_sort(arr, mid + 1, right);

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