1
\$\begingroup\$

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 < 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 <= 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 < sorted.length; i++) {

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

                break;
            }

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

                break;
            }

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


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

        }
        return sorted;


    }
\$\endgroup\$
2
\$\begingroup\$

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

while (index1 < subArray1.length && index2 < subArray2.length){
    if (subArray1[index1] <= 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.

\$\endgroup\$
1
\$\begingroup\$

You create too many arrays while sorting. You create a copy, then make a recursive call, where another copy is created (although only for a half of the original size), and then do it again all the way down to the bottom. Then the same is repeated for another half of the array. So for large arrays you would create too much pressure on the GC.

If you are not against reading some C++, then you could take a look at how to save on memory allocation in my answer to this question:

Implementation of the merge_sort - comparing the timing of an array versus a vector

In that sample the array is sorted in place. As your approach is to return a new array, then to adapt my solution you could make a copy at the start, sort it in place, and return it. For sorting you will need aux storage as well. All in all it is enough to create just 3 arrays - 1 for the result array and 2 for aux storage. The aux storage is reused on every level of recursion.

\$\endgroup\$
0
\$\begingroup\$

Continuing your style, you may want to consider the following:

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

public class MergeSort {

    private static final int LARGE = 1000000;

    public static void main(String[] args) {

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

        for (int i=0; i < 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));
        System.out.println("Is sorted: " + isSorted(arr));

        arr = new int[LARGE];

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

        final int[] arr2 = arr.clone();

        start = System.currentTimeMillis();
        arr = merge(arr).clone();
        end = System.currentTimeMillis();

        System.out.println("Your method took " + (end - start) + " ms. " + 
                           "Sorted: " + isSorted(arr));

        start = System.currentTimeMillis();
        Arrays.sort(arr2);
        end = System.currentTimeMillis();

        System.out.println("JDK sort took " + (end - start) + " ms. Sorted: " +
                           isSorted(arr2));
    }

    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 <= 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[array.length];

        int index1 = 0;
        int index2 = 0;
        int i = 0;

        while (index1 < subArray1.length && index2 < subArray2.length) {
            sorted[i++] = 
                    subArray1[index1] <= subArray2[index2] ?
                    subArray1[index1++] :
                    subArray2[index2++];
        }

        // Case 1: right subarray was exhausted first.
        while (index1 < subArray1.length) {
            sorted[i++] = subArray1[index1++];
        }

        // Case 2: left subarray was exhausted first.
        while (index2 < subArray2.length) {
            sorted[i++] = subArray2[index2++];
        }

        // Out of two cases (1 and 2) only one will actually iterate.
        return sorted;
    }

    private static boolean isSorted(final int[] array) {
        for (int i = 0; i < array.length - 1; ++i) {
            if (array[i] > array[i + 1]) {
                return false;
            }
        }

        return true;
    }
}

The only issue left is that your implementation is around two times slower that a JDK merge sort and that's because you are doing a superfluous "array magic". An efficient implementation of merge sort can be implemented to use only one auxiliary array. See, for instance, the source for java.util.Arrays.java.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.