迭代合并排序似乎不正确 - 产生有效的输出

Question

我知道迭代merge sort可以在网上找到，但是我创建的这个实现似乎与我在网上看到的例子大不相同。

这是我所拥有的。我迭代地实现了这个，但认为它不正确，因为这不是recursive实现所遵循的。

递归实现splits/sorts一半然后另一个然后合并。此实现对整个列表进行拆分/排序，然后将它们与stack.

我的问题是，这是一个正确的迭代实现吗？

我想我应该使用 aqueue而不是 a stack。

public static List<Integer> iterativeMergeSort(List<Integer> nums){

    Stack<List<Integer>> stack = new Stack<List<Integer>>();

    for (int num : nums) {

        stack.push(new ArrayList<Integer>(Arrays.asList(num)));

    }

    while (stack.size() > 1) {

        List<Integer> a = stack.pop();

        List<Integer> b = stack.pop();

        stack.push(merge(a,b));

    }

    return stack.pop();

}

public static List<Integer> merge(List<Integer> a, List<Integer> b) {

    int i = 0;

    int j = 0;

    List<Integer> merged = new ArrayList<Integer>();

    while (i < a.size() && j < b.size()) {

        if (a.get(i) == b.get(j)) {

            merged.add(a.get(i));

            merged.add(b.get(j));

            i++;

            j++;

        }

        else if (a.get(i) < b.get(j)) {

            merged.add(a.get(i));

            i++;

        }

        else { //a.get(i) > b.get(j)

            merged.add(b.get(j));

            j++;

        }

    }

    while (i < a.size()) {

        merged.add(a.get(i));

        i++;

    }

    while (j < b.size()) {

        merged.add(b.get(j));

        j++;

    }

    return merged;

}

Answer 1

迭代归并排序通常是自下而上的。与使用重复递归拆分数组不同，自底向上归并排序跳过该步骤并将 n 个元素的数组视为大小为 1 的 n 次运行，并立即开始合并运行。自顶向下归并排序只会拆分子运行，直到在执行任何合并之前产生两个大小为 1 的子运行为止，并且速度稍慢，这就是为什么大多数库使用自下而上归并排序的一些变体的原因。Wiki 文章包含用于自底向上归并排序的伪代码：https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation可以通过交换指针或引用而不是复制来避免复制回步骤。

Answer 2

这个实现对我来说是错误的。这更像是一个插入排序（https://en.wikipedia.org/wiki/Insertion_sort）。合并排序的想法是将数据分成 2 个接近偶数的组，但此实现并没有这样做。您的 'a' 基本上是先前排序的元素的列表，而 'b' 是要添加的下一个元素。