Merge sort implementation: sorting feels clunky I got bored and decided to make a merge sort from scratch.  I like everything, except for my "merging" of the two arrays into a sorted array inside the for loop.  I had several bugs that I had to iron out, which were along the lines of if subArray1 or subArray2 ran out of elements, checking them caused ArrayOutOfBoundsException.  This prompted me to add the two ifs above the sorting to finish the sorting.

Is there a better / less clunky way to "merge" the two arrays together?

import java.util.Arrays;
import java.util.Random;

public class MergeSort {

    public static void main(String[] args) {

        Random random = new Random();
        int max = 10000;
        int arr[] = new int[max];

        for (int i=0; i &lt; max; i++) {
            arr[i] = random.nextInt(2147483647);
        }

        System.out.println("boop!");
        long start = System.currentTimeMillis();
        arr = merge(arr).clone();
        long end = System.currentTimeMillis();

        System.out.println("it took " + (end - start) + " milliseconds");
        System.out.println(Arrays.toString(arr));


    }

    public static int[] merge(int[] array) {

        int maxIndex = array.length;
        int halfIndex = (array.length) / 2;


        // if the array was split into one
        if (array.length &lt;= 1) {
            return array;
        }

        int[] subArray1;
        int[] subArray2;
        int[] sorted;

        subArray1 = Arrays.copyOfRange(array, 0, halfIndex);
        subArray2 = Arrays.copyOfRange(array, halfIndex, maxIndex);

        subArray1 = merge(subArray1);
        subArray2 = merge(subArray2);


        sorted = new int[subArray1.length + subArray2.length];


        int index1 = 0, index2 = 0;
        for (int i = 0; i &lt; sorted.length; i++) {

            // if subArray1 ran out of elements
            if (index1 == subArray1.length) {
                for (; i &lt; sorted.length; i++) {
                    sorted[i] = subArray2[index2++];
                }

                break;
            }

            // if subArray2 ran out of elements
            if (index2 == subArray2.length) {
                for(; i &lt; sorted.length; i++) {
                    sorted[i] = subArray1[index1++];
                }

                break;
            }

            if (subArray1[index1] &lt;= subArray2[index2]) {
                sorted[i] = subArray1[index1++];
                continue;
            }


            if (subArray1[index1] &gt; subArray2[index2]) {
                sorted[i] = subArray2[index2++];
                continue;
            }

        }
        return sorted;


    }
That merge would be clearer as a while (index1 &lt; subArray1.length &amp;&amp; index2 &lt; subArray2.length), while bot arrays have elements to be merged in. And you can do 2 System.arraycopys for the remainder afterwards.

while (index1 &lt; subArray1.length &amp;&amp; index2 &lt; subArray2.length){
    if (subArray1[index1] &lt;= subArray2[index2]) {
        sorted[i++] = subArray1[index1++];
    else {
        sorted[i++] = subArray2[index2++];
}

System.arraycopy(subArray1, index1, sorted, i, subArray1.length - index1);
i+=subArray1.length - index1;

System.arraycopy(subArray2, index2, sorted, i, subArray2.length - index2);


At the end either subArray1.length - index1 or subArray2.length - index2 would be 0 but then the arraycopy will be a no-op.