归并排序的非递归实现

递归 vs 非递归

算法思路：初始每个元素为长度 1 的有序子表；第 1 趟两两归并为长度 2；第 2 趟归并为长度 4；…… 直到归并长度 $\geq n$。

void MergeSort_NonRecursive(int A[], int n) {
    int *temp = (int*)malloc(n * sizeof(int));
    for (int len = 1; len < n; len *= 2) {   // 归并长度倍增
        for (int i = 0; i < n; i += 2*len) {  // 每次处理 2*len 个元素
            int left  = i;
            int mid   = min(i + len, n);      // 边界截断
            int right = min(i + 2*len, n);    // 边界截断
            Merge(A, temp, left, mid, right);
        }
    }
    free(temp);
}

• 边界处理：mid、right 不能超过 n，用 min 截断。
• 最后一组不完整：剩余不足 2·len 时 mid 或 right 截断到 n。
• 辅助数组：每次 merge 需 O(n) 额外空间。