Using Stacks for a Non-Recursive MergeSort?

Question

my professor assigned a problem in which we must use Stacks (or Queues) to make 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'm not sure how to approach this problem, and any help would be appreciated. I know that i must use a while loop to emulate the recursion. But how can I split the actual values? Also, how can I keep track of the middle of the partitioned values?

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

Answer 1

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

Conceptually, a merge sort works as follows:

Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted). Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Solution 1: With a 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 bit more complex.

It basically consists on merging the elements of the first stack, inserting them into the second stack, until 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,