Simple Java mergeSort implementation

Question

public class MergeSortImplementation {

    public static int[] merge(int[] arrayA, int[] arrayB) {
        int n = arrayA.length + arrayB.length;

        int[] mergedArray = new int[n];

        int x = 0;
        int y = 0;
        int a = 0;
        int b = 0;

        for (int i = 0; i < mergedArray.length; i++) {

            // Check if arrayA is out of bounds.
            if (x < arrayA.length) {
                a = arrayA[x];
            } else {
                b = arrayB[y];
                mergedArray[i] = b;
                y++;
                continue;
            }

            // Check if arrayB is out of bounds.
            if (y < arrayB.length) {
                b = arrayB[y];
            } else {
                a = arrayA[x];
                mergedArray[i] = a;
                x++;
                continue;
            }

            if (a == b) {
                mergedArray[i] = a;
                i++;
                x++;
                mergedArray[i] = b;
                y++;
            } else if (a < b) {
                mergedArray[i] = a;
                x++;
            } else if (b < a) {
                mergedArray[i] = b;
                y++;
            }
        }

        return mergedArray;
    }

    public static int[] mergeSort(int[] inputArr) {

        int n = inputArr.length;

        // Base Case: Array's length is less than 1 
        if (n <= 1) {
            return inputArr;
        }

        // Creating two arrays to store values
        int[] arrayA = new int[n / 2];
        int[] arrayB = new int[n - (n / 2)];

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

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

        // Initializing arrayB
        for (int i = 0; i < 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;
    }

    public static void main(String[] args) {

        int[] intArr = {49, 23, 59, 23, 49, 32};

        int[] sortedArray = mergeSort(intArr);

        for (int e : sortedArray) {
            System.out.print(e + " ");
        }
    }
}

It looks very different from others. This is because I am creating an extra array and returning another. Other than memory/space inefficiency can someone tell me what could be better with the way I'm implementing MergeSort? Or why this coding style is not acceptable?

Answer 1

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 < first.length && secondIndex < second.length) {
        if (first[firstIndex] < second[secondIndex]) {
            merged[index++] = first[firstIndex++];
        } else {
            merged[index++] = second[secondIndex++];
        }
    }

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

    while (secondIndex < 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 < arrayA.length; i++) {
        arrayA[i] = inputArr[i];
    }

    // Initializing arrayB
    for (int i = 0; i < 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.

Answer 2

API:

Your API is a little bit off. java.util.Arrays implements all the sorting methods as static methods that do not return a sorted copy, but, instead, sort the input array.

Performance:

What comes to performance, you can make your implementation faster simply by allocating an auxiliary array only once before actual sorting. So, in the topmost call you request the sort to merge from an auxiliary array to the actual input array. These called implementation routines than swap the roles of the two arrays, and so on.

All in all:

public class MergeSortImplementation {

    public static int[] merge(int[] arrayA, int[] arrayB) {
        ... // Your merge method.
    }

    public static int[] mergeSort(int[] inputArr) {
        ... // Your merge sort.
    }

    public static void coderoddeMergesort(int[] array) {
        coderoddeMergesort(array, 0, array.length);
    }

    public static void coderoddeMergesort(int[] array, 
                                          int fromIndex, 
                                          int toIndex) {
        int rangeLength = toIndex - fromIndex;

        if (rangeLength < 2) {
            return;
        }

        int[] buffer = Arrays.copyOfRange(array, fromIndex, toIndex);
        coderoddeMergesort(buffer, array, 0, fromIndex, rangeLength);
    }

    private static void coderoddeMergesort(int[] source,
                                           int[] target,
                                           int sourceOffset,
                                           int targetOffset,
                                           int rangeLength) {
        if (rangeLength < 2) {
            return;
        }

        int middle = rangeLength >>> 1;

        coderoddeMergesort(target, source, targetOffset, sourceOffset, middle);
        coderoddeMergesort(target,
                           source, 
                           targetOffset + middle,
                           sourceOffset + middle,
                           rangeLength - middle);

        coderoddeMerge(source, 
                       target,
                       sourceOffset,
                       targetOffset,
                       middle,
                       rangeLength - middle);
    }

    private static void coderoddeMerge(int[] source,
                                       int[] target,
                                       int sourceOffset,
                                       int targetOffset,
                                       int leftRunLength,
                                       int rightRunLength) {
        int targetIndex = targetOffset;
        int left        = sourceOffset;
        int leftBound   = left + leftRunLength;
        int right       = leftBound;
        int rightBound  = right + rightRunLength;

        while (left < leftBound && right < rightBound) {
            target[targetIndex++] =
                    source[left] < source[right] ?
                    source[left++] :
                    source[right++];
        }

        System.arraycopy(source, left, target, targetIndex, leftBound - left);
        System.arraycopy(source,
                         right, 
                         target, 
                         targetIndex, 
                         rightBound - right);
    }

    private static final int SIZE = 1_000_000;

    public static void main(String[] args) {
        long seed = System.nanoTime();
        Random random = new Random(seed);

        // Warm the JVM up.
        for (int i = 0; i < 10; ++i) {
            int[] arr = getRandomArray(10_000, random);
            int[] arr2 = arr.clone();
            mergeSort(arr);
            coderoddeMergesort(arr2);
        }

        int[] array1 = getRandomArray(SIZE, random);
        int[] array2 = array1.clone();

        System.out.println("Seed = " + seed);

        long startTime = System.nanoTime();
        int[] sorted = mergeSort(array1);
        long endTime = System.nanoTime();

        System.out.printf("mergeSort in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        startTime = System.nanoTime();
        coderoddeMergesort(array2);
        endTime = System.nanoTime();

        System.out.printf("coderoddeMergesort in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        System.out.println("Arrays are identical: " + 
                Arrays.equals(sorted, array2));
    }

    private static int[] getRandomArray(int size, Random random) {
        int[] array = new int[size];

        for (int i = 0; i < size; ++i) {
            array[i] = random.nextInt();
        }

        return array;
    }
}

The above implementation improves performance of your version by a factor of at least two:

Seed = 39329736750162
mergeSort in 463.74 milliseconds.
coderoddeMergesort in 183.65 milliseconds.
Arrays are identical: true