1
\$\begingroup\$

Could I ask you to evaluate my implementation of mergesort?

I think that it's consistent with \$\mathcal{O}(n \log n)\$ complexity but has a downside that I create a new result array at each step of recursion.

How do you think it can be improved?

public int[] mergesort(final int[] input) {
    return mergesort(input, 0, input.length - 1);
}

private int[] mergesort(final int[] input, final int left, final int right) {
    final int[] result;
    if (left < right) {
        final int m = (right - left) / 2 + left;
        final int[] leftPart = mergesort(input, left, m);
        final int[] rightPart = mergesort(input, m + 1, right);
        result = new int[leftPart.length + rightPart.length];
        int i = 0, j = 0;
        while (i < leftPart.length && j < rightPart.length) {
            if (leftPart[i] <= rightPart[j]) {
                result[i + j] = leftPart[i++];
            } else {
                result[i + j] = rightPart[j++];
            }
        }
        while (i < leftPart.length) {
            result[i + j] = leftPart[i++];
        }
        while (j < rightPart.length) {
            result[i + j] = rightPart[j++];
        }
    } else {
        result = new int[]{input[left]};
    }
    return result;
}
\$\endgroup\$
1
\$\begingroup\$

First things first: Why are you returning a new array instead of directly sorting the input array? If we create 2 temporary arrays (left and right part) and then merge them back into the input array we don't need to return a new one (and can optimise later on).

private static void mergesort(int[] input, final int left, final int right) {
    //quick note here, I flipped your if check so we can return earlier.
    //This makes it easier to follow the complete flow
    if (left >= right) {
        return;
    }
    //edge cases handled before this point. Can continue with actual algorithm after.
    final int m = (right - left) / 2 + left;
    mergesort(input, left, m);
    mergesort(input, m + 1, right);

    int[] leftPart = new int[m - left + 1];
    for(int i = 0; i < leftPart.length-1;i++){
        leftPart[i] = input[left + i];
    }
    int[] rightPart = new int[right - m];
    for(int i = 0; i<rightPart.length-1;i++){
        rightPart[i] = input[m + i];
    }

    int i = 0, j = 0;
    while (i < leftPart.length && j < rightPart.length) {
        if (leftPart[i] <= rightPart[j]) {
            input[i + j] = leftPart[i++];
        } else {
            input[i + j] = rightPart[j++];
        }
    }
    while (i < leftPart.length) {
        input[i + j] = leftPart[i++];
    }
    while (j < rightPart.length) {
        input[i + j] = rightPart[j++];
    }
}

Now that we sort the input array directly theres one major memory optimisation we can do. We no longer need to store the right half in a temporary array anymore. Instead we can directly copy from the input array since the "current" spot is always smaller or equal than the index of the right part we're handling.

private static void mergesort(int[] input, final int left, final int right) {
    if (left >= right) {
        return;
    }

    final int m = (right - left) / 2 + left;
    mergesort(input, left, m);
    mergesort(input, m + 1, right);

    int[] leftPart = new int[m - left+1];
    //note: arraycopy is usually more efficient than manually copying an array.
    System.arraycopy(input, left, leftPart, 0, leftPart.length);

    int current = left;
    int currentLeft = 0;
    int currentRight = m+1;

    while (currentLeft < leftPart.length && currentRight <= right) {
        if (leftPart[currentLeft] <= input[currentRight]) {
            input[current++] = leftPart[currentLeft++];
        } else {
            input[current++] = input[currentRight++];
        }
    }
    while (currentLeft < leftPart.length) {
        input[current++] = leftPart[currentLeft++];
    }
    //no need to handle remaining right part, as it's already in the input array
}

Some extra notes:

I renamed some variables to make it more clear what they mean. Even though i and j are common enough for a simple loop, it wasn't obvious enough anymore once the right index started from halfway the part of the array that needed to be sorted.

I made the method static. It doesn't depend on any state of the class it's in so could be put into a more general utility class instead.

System.arraycopy is more performant than manually copying all elements into another array.

\$\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.