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

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' 是要添加的下一个元素。