Using stacks for non-recursive MergeSort?

Question

My professor has identified a problem in which we must use Stacks (or Queues) to create a non-recursive MergeSort. The current code is as follows:

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); 

I am not sure how to approach this problem, and any help will be appreciated. I know that I should use a while loop to emulate recursion. But how can I separate the actual values? Also, how can I track the middle of the divided values?

I am really confused by this problem. Any help would be appreciated!

Answer 1

The most important thing is to understand how the algorithm works. From Wikipedia :

Conceptually, merge sort works as follows:

Divide the unsorted list into n subscriptions, each of which contains 1 element (a list of 1 element is considered sorted). Repeatedly merge sub-lists - create new sorted sub-lists until only 1 subnet remains. This will be a sorted list.

Solution 1 : with the queue.

---

 static int[] mergeSortQueue(int[] A) { Queue<int[]> queue = new LinkedList<int[]>(); 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(); } 

---

Graphically

---

Solution 2 : with two stacks

---

This is a little trickier.

Basically, it consists in combining the elements of the first stack, inserting them into the second stack, while only one remains.

 static int[] mergeSortStacks(int[] A) { Stack<int[]> stack = new Stack<int[]>(); Stack<int[]> stack2 = new Stack<int[]>(); 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(); } 

---

Graphically