Merge Sort with Java, confusing behaviours in the merge step

While I was trying the merge sort algorithm with Java, there are yet unclear behaviors occurring in the process.

The algorithm works fine, no issue, I'm here to get some clarifications about the algorithm that is not behaving up to my expectations.
This is the same merge sort algorithm, the only difference is I'm using Java's "BigInteger" type for my specific problem solution. So the algorithm is sorting based on the type BigInteger therefore some small extra steps are there...

First let's check the code I've written.


import java.math.BigInteger;
import java.util.Arrays;
import java.util.List;

public class MergeSorter {
    public BigInteger[] Merge_Sort(BigInteger[] Arr, int start,  int end){
        if(start<end){
            int mid = (start+end)/2;
            Merge_Sort(Arr, start, mid);
            Merge_Sort(Arr, mid+1, end);
            Merge(Arr, start,mid, end);
        }
        return Arr;
    }

    public void Merge(BigInteger[] Arr, int start, int mid, int end){
        int n1 = mid - start+1;
        int n2 = end - mid;

        BigInteger[] left = new BigInteger[n1+1];
        BigInteger[] right = new BigInteger[n2+1];

        for(int i=0; i<n1; i++){
            left[i] = Arr[start+i-1];
        }

        for(int j=0; j<n2; j++){
            right[j] = Arr[mid+j];
        }

        left[n1] =  null;
        right[n2] = null;

        int i=0;
        int j=0;
        for(int k=start-1;k<end; k++ ){
            if(left[i]!=null && right[j]!=null){
                if((left[i].compareTo(right[j])==-1)
                        ||(left[i].compareTo(right[j])==0)){
                    Arr[k] = left[i];
                    i++;
                }else{
                    Arr[k] = right[j];
                    j++;
                }
            }else if(right[j]!=null){
                Arr[k] = right[j];
                j++;
            }else if(left[i]!=null){
                Arr[k] = left[i];
                i++;
            }else{
                break;
            }
        }
    }
}

What is boiling my brain? (How and what is the problem)

At the merge step, Merge(Arr, start, mid, end); we are using the recursion to run with start, mid and end variable values, however, there's something like "magical" happening in here, that is,
HOW IS THE ARRAY GETTING SORTED WITHOUT EVEN RETURNING, OR AM I MISSING SOME MORE KNOWLEDGE ABOUT RECURSION?...

That is where I'm stuck...

I tried some naive method to expose the behavior as well as below:

public void printer(int inc, int start, int mid, int end){
    inc++;
    System.out.println("inc: "+inc);
    System.out.println("Merge Step Runs with: "+"Start: "+start+" mid: "+mid+" end: "+end);
}

public void Merge_Sort(int inc, int start,  int end){
    if(start<end){
        int mid = (start+end)/2;
        Merge_Sort( inc, start, mid);
        Merge_Sort( inc, mid+1, end);

        printer( inc,start, mid, end);
    }
}

Things doesn't add up, inc does not get replaced as the array in merge sort does.

Would love to hear from you for further references for a good read if there's any in relevance to this context.

Solution

How is the array getting sorted without even returning

The parameter Arr is a reference to an array, so when Merge() writes to Arr (Arr[...] = ...), it updates the original array. The parameter inc is a primitive, so it is passed by value (a copy of it is made).

You might want to consider changing the merge sort to do less copying. A top down merge sort can be implemented with a one time copy of the entire array, or a bottom up merge sort can be implemented without any copying, just a second working array.

https://en.wikipedia.org/wiki/Merge_sort