使用Stacks进行非递归MergeSort？

我的教授分配了一个问题，我们必须使用Stacks（或Queues）来创建一个非递归的MergeSort。 目前的代码如下：

private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a, index, aux, lo, mid); sort(a, index, aux, mid + 1, hi); merge(a, index, aux, lo, mid, hi); 

我不知道如何处理这个问题，任何帮助将不胜感激。 我知道我必须使用while循环来模拟递归。 但是，我如何分割实际值？ 另外，如何跟踪分区值的中间值？

我真的很困惑这个问题。 任何帮助，将不胜感激！

Answer 1

最重要的是要了解算法的工作原理。 来自维基百科 ：

从概念上讲，合并排序的工作原理如下：

将未排序的列表分成n个子列表，每个子列表包含1个元素（1个元素的列表被视为已排序）。 重复合并子列表以生成新的已排序子列表，直到只剩下1个子列表。 这将是排序列表。

解决方案1 ：使用队列。

---

 static int[] mergeSortQueue(int[] A) { Queue queue = new LinkedList(); for (int i = 0; i < A.length; i++) { queue.add(new int[]{A[i]}); } while (queue.size()>1) { int[] r = queue.poll(); int[] l = queue.poll(); int[] merged=merge(l, r); queue.add(merged); } return queue.poll(); } 

---

从图形上看，

---

解决方案2 ：使用两个堆栈

---

这有点复杂。

它基本上包括合并第一个堆栈的元素，将它们插入第二个堆栈，直到只剩下一个。

 static int[] mergeSortStacks(int[] A) { Stack stack = new Stack(); Stack stack2 = new Stack(); for (int i = 0; i < A.length; i++) { stack.push(new int[]{A[i]}); } while (stack.size()>1) { while (stack.size()>1) { int[] r = stack.pop(); int[] l = stack.pop(); int[] merged=merge(l, r); stack2.push(merged); } while (stack2.size()>1) { int[] r = stack2.pop(); int[] l = stack2.pop(); int[] merged=merge(l, r); stack.push(merged); } } return stack.isEmpty() ? stack2.pop() : stack.pop(); } 

---

从图形上看，