MergeSort.java

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        int[] numbers = {-10, 2, 100, 43 ,4, 0, 1};

        System.out.println(Arrays.toString(numbers));
        int[] sorted = mergeSort(numbers);
        System.out.println(Arrays.toString(sorted));
    }

    /*
    we calculate a middle pivot point to sort, which involves allocating two subarrays with a total combined length
    equivalent to the length of the original array
    */
    private static int[] mergeSort(int[] numbers) {
        int n = numbers.length;
        if(n <= 1) return numbers;
        int mid = n/2;
        int[] left = new int[mid];
        int[] right = new int[n - mid];

        for(int i = 0; i < left.length; i++) {
            left[i] = numbers[i];
        }

        for(int i = 0; i < right.length; i++){
            right[i] = numbers[i+mid];
        }

        return merge(mergeSort(left), mergeSort(right));
    }

    private static int[] merge(int[] l, int[] r) {
        int[] merged = new int[l.length + r.length];

        int i = 0, j = 0; //two variables to iterate through both subarrays, i is for left, j is for right

        for (int k = 0; k < merged.length; k++) {
            if(i >= l.length)
                merged[k] = r[j++];
            else if(j >= r.length)
                merged[k] = l[i++];
            else if(l[i] <= r[j])
                merged[k] = l[i++];
            else
                merged[k] = r[j++];
        }

        return merged;
    }
}