Recursive method in java merge sorting algorithm

I have the following merge sort code in my application. I am very confused about how the recursive method is called again after it exits the if block when the if condition fails. I have debugged my code but still don't get it. The sort method that calls mergesort (0, number-1) starts first with mergesort (0, 5). low is high, medium is 2, so nexts (0, 2) runs. This continues until we have mergesort (0, 0), in which case the low is not lower, so it exits the if block. But when I debug, the method returns and it runs again after the mergesort (0, 0) case. How will the call be repeated? Please help me. Thanks for taking the time to read my question :)

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

    private int number;


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

    private int[] mergesort(int low, int high) {
        // check if low is smaller then 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);
        }
        return numbers;
    }

    private int[] 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++;
        }
        return numbers;

    }
}

      

+3


source to share


1 answer


This is because the method mergesort

calls itself twice. You can print the stack to see what happens.



For example, when called mergesort(0,1)

, the method will be called first mergesort(0,0)

and then mergesort(1,1)

.

+2


source







All Articles