How will the stack be formed by Recursion in the MergeSort function?

Question

This is the Merge Sort code:

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};

        System.out.println("Unsorted Array:");
        printArray(arr);

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("Sorted Array:");
        printArray(arr);
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;

            mergeSort(arr, left, middle);
            mergeSort(arr, middle + 1, right);

            merge(arr, left, middle, right);
        }
    }

    public static void merge(int[] arr, int left, int middle, int right) {
        int n1 = middle - left + 1;
        int n2 = right - middle;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        for (int i = 0; i < n1; i++) {
            leftArray[i] = arr[left + i];
        }
        for (int i = 0; i < n2; i++) {
            rightArray[i] = arr[middle + 1 + i];
        }

        int i = 0, j = 0;
        int k = left;

        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

I am specifically looking at the mergeSort(int[] arr, int left, int right) function which recursively calls itself and divides the array using the middle index or m. I am having trouble understanding how the stack will be formed since there are back to back two recursive statements and a call to the merge function. For instance, if there is an int[] array = [5, 4, 6, 7, 8, 2, 1] and r and l are array.length - 1 and 0 respectively, then the base condition is satisfied, m = 3 and the first recursive call is made which assigns m to right. Then the same recursive call is made until the base condition is not satisfied.Once the base condition is not satisfied, the second recursive call is made. I am not sure if the second recursive call is made side by side the first one and what that stack will look like, and in what order will merge be called on the 'subarrays'. Please help by showing what the stack would look like for the aforementioned array and in what order will merge be called on them. Thank you!

Answer 1

I am having trouble understanding how the stack will be formed since there are back to back two recursive statements and a call to the merge function

It's immaterial how many recursive (or non-recursive) subcalls are made from a function as far as the stack is concerned. If a function has two recursive calls, the first recursive call must completely finish (i.e. clear the stack frames it created) before the second recursive call begins on a totally fresh "sub-stack" (if you will). Stacks can only push or pop, so it's not like the stack splits into two or anything like that.

I am not sure if the second recursive call is made side by side the first one and what that stack will look like, and in what order will merge be called on the 'subarrays'

As mentioned above, multiple recursive calls happen in series, not parallel or "side by side". The left subarray call chain runs, clears and then the right subarray chain takes its place on the stack, running and clearing.

Recursion isn't necessary to understand this. Consider the following pseudocode:

function bar() {}
function baz() {}
function foo() {
  bar();
  baz();
}
foo();

The stack will be:

1. [] (initially empty)
2. [foo] (call foo())
3. [foo, bar] (call bar() from foo(), pausing foo())
4. [foo] (complete bar(), returning control to foo() momentarily)
5. [foo, baz] (call baz() from foo(), pausing foo())
6. [foo] (complete baz(), returning control to foo())
7. [] (complete foo(), popping the last item from the call stack)

So bar and baz will never be on the stack at the same time.

I'm not sure what you mean by "what order will merge be called on the subarrays", but merge isn't called until both subarrays are sorted recursively and the calls spawned by the current call to mergeSort are completed. merge then, well, merges the two subarrays into one sorted subarray, fulfilling mergeSort's obligation to its parent frame (sorting its subarray) and returning control to that parent frame, which is paused waiting for its child call to finish. Once it regains control, the parent call will then begin work on its right subchild or merge its sorted subarrays, depending on where its execution was blocked.

Here's what the call stack would look like on an array with 6 elements, similar to yours (the whole array is passed through the calls, so that's always the same and can be ignored for the purposes of call stack visualization):

const printStack = (s, action) => {
  s = [
    ...s.slice(0, -1),
    `${s.at(-1)} (${action})`,
  ];
  console.log(s.reverse().join("\n"));
}

const f = (lo, hi, stack=[]) => {
  stack.push(`f(${lo}, ${hi})`);
  printStack(stack, "push");

  if (lo < hi) {
    let mid = Math.floor((lo + hi) / 2);
    f(lo, mid, stack);
    f(mid + 1, hi, stack);
  }

  printStack(stack, "pop");
  stack.pop();
};

f(0, 6);

Another common way to visualize the calls is:

const f = (lo, hi, depth=0) => {
  const p = "  ".repeat(depth);
  console.log(`${p}push: f(${lo}, ${hi})`);

  if (lo < hi) {
    let mid = Math.floor((lo + hi) / 2);
    f(lo, mid, depth + 1);
    f(mid + 1, hi, depth + 1);
  }

  console.log(`${p}pop:  f(${lo}, ${hi})`);
};

f(0, 6);

In this visualizer, the current stack grows left to right. You can determine the current stack by following the left-right thread, keeping in mind that previous calls on the same level are already popped, not running in parallel. Adding animation can help clarify the behavior:

const sleep = ms => new Promise(r => setTimeout(r, ms));
const delay = 1000;

const f = async (lo, hi, depth=0) => {
  const p = "  ".repeat(depth);
  console.log(`${p}push: f(${lo}, ${hi})`);
  await sleep(delay);

  if (lo < hi) {
    let mid = Math.floor((lo + hi) / 2);
    await f(lo, mid, depth + 1);
    await f(mid + 1, hi, depth + 1);
  }

  console.log(`${p}pop:  f(${lo}, ${hi})`);
  await sleep(delay);
};

f(0, 6);