如何修改迭代式归并排序算法以支持非2的幂次输入规模？

你的迭代式归并排序代码核心有两个致命问题：一是外层循环没覆盖非2幂次长度的剩余元素，二是合并时的边界计算逻辑错误。下面是具体修复方案：

核心问题分析 #

1. 外层循环逻辑缺陷：原代码从size=2开始，且循环条件为size <=n，当数组长度不是2的幂次时，最后一组不足size的元素完全没被处理（比如长度9时，最后1个元素永远不会进入合并逻辑）。
2. 边界计算错误：Merge方法里依赖静态变量arr.length判断边界，但source可能是临时数组dest，会导致越界；而且三元运算符的逻辑完全错误，导致第二个子数组的结束位置计算偏差。

修复后的完整代码 #

public class ChangeStatic {
    static int[] arr = {4, 2, 7, 6, 3, 0, 5, 1, 9}; // 测试非2幂次长度数组
    public static void main(String[] args) {
        System.out.println("Original: ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        Iteration();
        System.out.println();
        System.out.println("Sorted: ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void Iteration() {
        int n = arr.length;
        int[] dest = new int[n];
        // 从单个元素开始合并，size是当前有序块的大小
        for (int size = 1; size < n; size *= 2) {
            // 遍历所有可合并的块对
            for (int left = 0; left < n; left += 2 * size) {
                int mid = left + size - 1;
                // 第二个块的结束位置不能超过数组最后一个索引
                int right = Math.min(left + 2 * size - 1, n - 1);
                // 如果mid超出数组范围，说明只剩单个块，直接拷贝
                if (mid < n) {
                    Merge(arr, dest, left, size, right);
                } else {
                    System.arraycopy(arr, left, dest, left, n - left);
                }
            }
            // 交换原数组和目标数组，下一轮合并用新的原数组
            int[] temp = arr;
            arr = dest;
            dest = temp;
        }
        // 非2幂次长度的数组，最后一次交换后结果可能在dest里，需要拷贝回原数组
        if ((n & -n) != n) {
            System.arraycopy(arr, 0, dest, 0, n);
            arr = dest;
        }
    }

    // 重构Merge方法，通过参数传入边界，解耦静态变量依赖
    public static void Merge(int[] source, int[] destination, int start, int len, int right) {
        int i = start;
        int j = start + len;
        int k = start;
        int endOfFirst = start + len - 1;

        // 合并两个有序子数组
        while (i <= endOfFirst && j <= right) {
            destination[k++] = source[i] < source[j] ? source[i++] : source[j++];
        }
        // 拷贝第一个子数组剩余元素
        while (i <= endOfFirst) {
            destination[k++] = source[i++];
        }
        // 拷贝第二个子数组剩余元素
        while (j <= right) {
            destination[k++] = source[j++];
        }
    }
}

关键修改说明 #

• 外层循环调整：从size=1开始（单个元素本身有序），循环条件改为size < n，确保所有可能的块大小都被处理。
• 边界安全处理：计算right时用Math.min确保不越界，当只剩单个块时直接拷贝，避免无效合并。
• Merge方法解耦：不再依赖静态数组arr，通过参数传入边界，逻辑更清晰，避免静态变量带来的上下文错误。
• 最后结果校验：通过位运算判断数组长度是否为2的幂次，非幂次情况下把临时数组的结果拷贝回原数组，保证最终排序结果正确。

内容的提问来源于stack exchange，提问作者Muhammad Ahmad