Simple Java mergeSort implementation
The merge method

The implementation of merge is difficult to understand.


Naming is one problem. a, b, x, y are hard to distinguish. Was a the value and x the index of the first array? Or the other way around? It's easy to get lost.
Another issue with naming is that arrayA and arrayB differ by one letter. It's recommended to avoid using similar variable names, as the human eye may overlook too minor differences. first and second would be unmistakable.
A loop with a long body, multiple continue statements, and multiple incremented variables, is generally hard to read. It's all too easy to get lost in this code.


A simpler, almost naive implementation of the same thing:

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

    int firstIndex = 0;
    int secondIndex = 0;
    int index = 0;

    while (firstIndex &lt; first.length &amp;&amp; secondIndex &lt; second.length) {
        if (first[firstIndex] &lt; second[secondIndex]) {
            merged[index++] = first[firstIndex++];
        } else {
            merged[index++] = second[secondIndex++];
        }
    }

    while (firstIndex &lt; first.length) {
        merged[index++] = first[firstIndex++];
    }

    while (secondIndex &lt; second.length) {
        merged[index++] = second[secondIndex++];
    }

    return merged;
}


Note that I also changed the visibility to private. This method is an implementation detail of your sorting algorithm, no need to expose it.

The mergeSort method

It's recommended to minimize the live time of variables: the number of lines between declaration and last use. In other words, declare variables right before they are needed, not sooner.

In mergeSort, look at outputArr:


    // Creating resulting array
    int[] outputArr = new int[n];

    // Initializing arrayA
    for (int i = 0; i &lt; arrayA.length; i++) {
        arrayA[i] = inputArr[i];
    }

    // Initializing arrayB
    for (int i = 0; i &lt; arrayB.length; i++) {
        arrayB[i] = inputArr[i + (n / 2)];
    }

    // Divide array into 2 halves
    arrayA = mergeSort(arrayA);
    arrayB = mergeSort(arrayB);
    outputArr = merge(arrayA, arrayB);

    return outputArr;



It's not used until much later in the method. Notice what happens when you delay the declaration as much as possible:

    // Creating resulting array
    int[] outputArr = new int[n];
    outputArr = merge(arrayA, arrayB);

    return outputArr;


Do you see a problem? A new array is allocated in new int[n], only to be thrown away. Such mistakes become visible when you delay the declaration as much as possible. The above can be reduced to:

    return merge(arrayA, arrayB);


Memory/space inefficiency

You asked for comments "other than this". That's not a good idea. Usually there's a good reason why obvious problems should be avoided.

A merge sort can be implemented with essentially the same algorithm, but without creating the half-arrays. You will still need an extra array to perform the merge step. But the number of arrays created will be reduced drastically.

The JDK has Arrays.sort and Collections.sort utility methods for sorting arrays and collections, respectively. Both operate in-place. Usually it's good to follow example practices of the JDK. If you don't want to destroy the original array/collection, you can create a simple wrapper that copies the original collection, sort the copy and return a copy.