MergeSort - Implementation

Question

After many recursive calls low becomes equal to high and the recursion breaks. What happens after that? Can anyone please explain. Merge procedure is clear to me: when mergesort(0,5) is called, it calls itself again: mergesort(0,2) and then mergesort(0,1). Finally mergesort(0,0) and then recursion breaks.

What happens after that? Where does the control go in the code? Where is stack used? Please help me.

public class MergeSort {
private int[] numbers;
private int[] helper;

private int number;

public void sort(int[] values) {
    this.numbers = values;
    number = values.length;
    this.helper = new int[number];
    mergesort(0, number - 1);
}

private void mergesort(int low, int high) {
    // check if low is smaller than high, if not then the array is sorted
    if (low < high) {
        // Get the index of the element which is in the middle
        int middle = low + (high - low) / 2;
        // Sort the left side of the array
        mergesort(low, middle);
        // Sort the right side of the array
        mergesort(middle + 1, high);
        // Combine them both
        merge(low, middle, high);
    }
}

private void merge(int low, int middle, int high) {

    // Copy both parts into the helper array
    for (int i = low; i <= high; i++) {
        helper[i] = numbers[i];
    }

    int i = low;
    int j = middle + 1;
    int k = low;
    // Copy the smallest values from either the left or the right side back
    // to the original array
    while (i <= middle && j <= high) {
        if (helper[i] <= helper[j]) {
            numbers[k] = helper[i];
            i++;
        } else {
            numbers[k] = helper[j];
            j++;
        }
        k++;
    }
    // Copy the rest of the left side of the array into the target array
    while (i <= middle) {
        numbers[k] = helper[i];
        k++;
        i++;
    }

}

 public static void main(String[] args){
     int arr[] = {78,9,45,7,2,90};
     new MergeSort().sort(arr);
        for(int i = 0; i < arr.length;i++){
            System.out.print(arr[i] + "\t");
        }
 }

}

Answer 1

For top down merge sort, no merging occurs until two runs of size 1 are produced from the recursive splitting of an array. This will be the first instance where the mergesort() calls merge(). Then that instance of mergesort() returns to the prior instance of mergesort(), eventually reaching it's call to merge() and so on. The merge order is depth first / left first.

By contrast, a bottom up merge sort (most libraries use some variation of bottom up merge sort like timsort), skips the recursion and treats an array of n elements as n runs of size 1, and immediately starts merging the runs. The indices to the runs are generated iteratively (via loops).

This is an example of the order of operations for a top down merge sort, which is depth first, left first. The vertical bars represent the split between left and right halves of the current array.

|4 2 8 6 0 5 1 7 3 9|
|4 2 8 6 0|5 1 7 3 9|
|4 2|8 6 0|
|4|2|
|2 4|
    |8|6 0|
      |6|0|
      |0 6|
    |0 6 8|
|0 2 4 6 8|
          |5 1|7 3 9|
          |5|1|
          |1 5|
              |7|3 9|
                |3|9|
                |3 9|
              |3 7 9|
          |1 3 5 7 9|
|0 1 2 3 4 5 6 7 8 9|

Answer 2

What happens is that every stacked method call is executed. If you represent graphically the stack you have the following in every step:

1.- bottom/top --> mergeSort(0, 5)

2.- top    --> mergeSort(0, 2)
    bottom --> mergeSort(0, 5)

3.- top    --> mergeSort(0, 1)
               mergeSort(0, 2)
    bottom --> mergeSort(0, 5)

4.- top    --> mergeSort(0, 0) --> breaks and go back
               mergeSort(0, 1)
               mergeSort(0, 2)
    bottom --> mergeSort(0, 5)

5.- top    --> mergeSort(0, 1) --> finish and continue with next line
               mergeSort(0, 2)
    bottom --> mergeSort(0, 5)

6.- top    --> mergeSort(2, 2) --> next line after mergeSort(0, 1)
               mergeSort(0, 2)
    bottom --> mergeSort(0, 5)

7.- etc.

With this first steps represented graphically, you can figure out the rest. Hope that helps

Answer 3

You could put else statement and observe that the executions are still done after low >= high. Here, these calls are just skipped.

        private void mergesort(int low, int high) { 
    // check if low is smaller than high, if not then the array is sorted
     if (low < high) { 
    // Get the index of the element which is in the middle 
int middle = low + (high - low) / 2; // Sort the left side of the array mergesort(low, middle); // Sort the right side of the array 
mergesort(middle + 1, high); // Combine them both 
merge(low, middle, high); }

    else 
    System.out.prinln("low is higher than high. Low is " +low+ "high is" +high);
     }