5
\$\begingroup\$

Is this a good implementation?

static int[] mergeSort(int[] arr) {
    if (arr.length <= 1) {
        return arr;
    }

    int[] left, right;

    left = Arrays.copyOfRange(arr, 0, arr.length / 2);
    right = Arrays.copyOfRange(arr, arr.length / 2, arr.length);

    left = mergeSort(left);
    right = mergeSort(right);

    return merge(left, right, arr);

}

private static int[] merge(int[] left, int[] right, int result[]) {

    int i = 0, j = 0, z = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result[z++] = left[i++];

        } else {
            result[z++] = right[j++];

        }
    }

    while (i < left.length) {
        result[z++] = left[i++];

    }
    while (j < right.length) {
        result[z++] = right[j++];

    }
    printArr(result);
    return result;

}
\$\endgroup\$
  • \$\begingroup\$ the size of right is arr.length. Doesn't hurt anything but bigger than you intended I think. \$\endgroup\$ – Hank D Apr 20 '16 at 21:59
  • \$\begingroup\$ this? right = new int[arr.length - arr.length / 2]; @HankD \$\endgroup\$ – Ayman Sherief Apr 20 '16 at 22:01
  • \$\begingroup\$ Calling mergeSort recursively all the way down to arrays of size 1 is overkill and inefficient. If it is required for an assignment, fine, but normally merge sorts split the data into reasonable chunks that can be sorted in memory by another algorithm. \$\endgroup\$ – Hank D Apr 20 '16 at 22:02
  • \$\begingroup\$ it works, but part of writing good code is to help the reader understand why you are doing what you are doing. The statement right = new int[arr.length - arr.length / 2]; doesn't convey to those reading your code that the size is "the size of the remaining elements from arr". Something that would make it clear might be right = new int[arr.length - left.length]; \$\endgroup\$ – Hank D Apr 20 '16 at 22:06
  • \$\begingroup\$ @HankD So using variables to store array sizes so as to make my code more self explanatory? Understood .. \$\endgroup\$ – Ayman Sherief Apr 20 '16 at 22:07
1
\$\begingroup\$

1

while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
        result[z++] = left[i++];

    } else {
        result[z++] = right[j++];

    }
}

while (i < left.length) {
    result[z++] = left[i++];
    // Why empty line right here??
}
while (j < right.length) {
    result[z++] = right[j++];

}

You should not have an empty line before a closing brace, but you should have one immediately after a closing brace, so you should rewrite this to

while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
        result[z++] = left[i++];
    } else {
        result[z++] = right[j++];
    }
}

while (i < left.length) {
    result[z++] = left[i++];
}

while (j < right.length) {
    result[z++] = right[j++];
}

2

Add public before static int[] mergeSort(int[] arr) since you possibly want to expose your sort outside the current package.

3

In JDK, the convention is that all sort class methods do not return the array (they all are declared void) but modify the contents of the input array.

4

Your implementation allocates \$\mathcal{O}(n \log n)\$ worth memory, whereas a linear space complexity suffices if you do a little trick (see Summa summarum). This slows down your algorithm since asking for memory is expensive, plus whenever we lose all references to an array, the garbage collector has to do additional work behind the scene in order to deallocate it.

What happens there, is that we allocate an auxiliary copy of the input array only once. Then, we distinguish two array roles: source anb target. Whenever merging, we read the data from source and put in sorted order to target. The actual mergesort routine alternates the roles of the arrays at each particular recursion level. This eliminates copying stuff in the merging routine, which increases performance.

Summa summarum

All in all, I had this in mind (rename if needed):

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

public static void coderoddeMergesort(final int[] array,
                                      final int fromIndex,
                                      final int toIndex) {

    if (fromIndex > toIndex) {
        throw new IllegalArgumentException(
                "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
    }

    final int rangeLength = toIndex - fromIndex;

    if (rangeLength < 2) {
        // Trivially sorted.
        return;
    }

    // Allocate the auxiliary buffer only ONCE.
    final int[] aux = Arrays.copyOfRange(array, fromIndex, toIndex);
    // Do actual sorting.
    coderoddeMergesortImpl(aux, 
                           array, 
                           0, 
                           rangeLength,
                           fromIndex,
                           toIndex);
}

private static void coderoddeMergesortImpl(final int[] source,
                                           final int[] target,
                                           final int sourceFromIndex,
                                           final int sourceToIndex,
                                           final int targetFromIndex,
                                           final int targetToIndex) {
    final int rangeLength = sourceToIndex - sourceFromIndex;

    if (rangeLength < 2) {
        return;
    }

    final int sourceMiddleIndex = sourceFromIndex + (rangeLength >>> 1);
    final int targetMiddleIndex = targetFromIndex + (rangeLength >>> 1);

    coderoddeMergesortImpl(target,
                           source,
                           targetFromIndex,
                           targetMiddleIndex,
                           sourceFromIndex,
                           sourceMiddleIndex);

    coderoddeMergesortImpl(target,
                           source,
                           targetMiddleIndex,
                           targetToIndex,
                           sourceMiddleIndex,
                           sourceToIndex);

    coderoddeMerge(source,
                   target,
                   targetFromIndex,
                   sourceFromIndex,
                   sourceMiddleIndex,
                   sourceToIndex);
}

private static void coderoddeMerge(final int[] source, 
                                   final int[] target,
                                   int targetOffset,
                                   int left,
                                   int right,
                                   final int rightBound) {
    final int leftBound = right;

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

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

(You can find a complete performance demonstration here.)

The performance figures are as follows:

coderoddeMergesort() in 1100 milliseconds.
mergeSort() in 1412 milliseconds.
Arrays are same: true

Hope that helps.

\$\endgroup\$
1
\$\begingroup\$
  static int[] mergeSort(int[] arr) {

If you want to call it array, please go ahead and write out the name.

Personally, I'd prefer data or numbers as names, but that may just be me.

    int[] left, right;

    left = Arrays.copyOfRange(arr, 0, arr.length / 2);
    right = Arrays.copyOfRange(arr, arr.length / 2, arr.length);

While this will work, consider

    int[] left = Arrays.copyOfRange(arr, 0, arr.length / 2);
    int[] right = Arrays.copyOfRange(arr, arr.length / 2, arr.length);

It's actually slightly shorter in this case, as int[] is shorter than left, right;. But even if it were longer, it is easier to follow with the declaration and initialization on the same line.

    int midpoint = arr.length / 2;

This could make it clearer why you are passing around arr.length / 2 if you replace occurrences with midpoint.

    int i = 0, j = 0, z = 0;

I would find this easier to read as either

    int i = 0,
        j = 0,
        z = 0;

or

    int i = 0;
    int j = 0;
    int z = 0;

One initialization per line.

    printArr(result);

This looks like debugging code to me. If so, it should have been removed before review.

I don't have any real comments on the algorithm itself beyond what people said in the comments. You might be able to bring down the memory usage if you tried hard enough, but it shouldn't generally matter. This is a more elegant version and less susceptible to bugs if you aren't memory bound.

You may be doing this just as an exercise (you can use the reinventing-the-wheel tag to indicate this) or for some other reason. In practice, the standard Arrays.sort implementation is good enough for most needs. You wouldn't normally need to roll your own.

\$\endgroup\$
  • \$\begingroup\$ I'm certainly Reinventing the wheel. I was just checking if there was any major flaw or anything. Thanks \$\endgroup\$ – Ayman Sherief Apr 21 '16 at 1:04
  • \$\begingroup\$ @mdfst13 I have a question related to algorithm here. Wanted to see if you can help me out. I have one solution but not sure if that's the best way to solve it. \$\endgroup\$ – user1950349 Jan 23 '18 at 3:34
0
\$\begingroup\$

A properly implemented Mergesort takes \$O(n \log n)\$ time and uses \$O(n)\$ extra memory. And while I think your code complies with those limits, the constants involved, especially when it comes to memory, are larger than needed

You typically want to write your algorithm to sort in-place (and precede it with a copy if you don't want to alter the input). This spares you lots of data copying ,which now only needs to happen in the merge step, and you actually only need to copy to a separate buffer the first half of the array. This also means that, once the merging is finished, any remaining items on the right side are already in the correct location and do not need to be copied back to the output.

I'm not sure if the written description is helping or just making things more confusing, so let me explain it in code:

static int[] mergeSort(int[] array) {
  int[] sortedArray = Arrays.copyOf(array, array.length);

  mergeSort(sortedArray, 0, sortedArray.length);
  return sortedArray;
}

private static void mergeSort(int[] array, int from, int to) {
  int midpoint = from + (to - from) / 2;

  if (to - from > 2)  {
    mergeSort(array, from, midpoint);
    mergeSort(array, midpoint, to);
  }
  merge(array, from, midpoint, to);
}

private static void merge(int[] array, int from, int midpoint, int to) {
  int[] tmp = Arrays.CopyOfRange(array, from, midpoint);
  int readLeftIndex = 0;
  int readRightIndex = midpoint;
  int writeIndex = from;

  while(readLeftIndex < tmp.length() && readRightIndex < to) {
    if (array[readRightIndex] < tmp[readLeftIndex]) {
      array[writeIndex++] = array[readRightIndex++];
    } else {
      array[writeIndex++] = tmp[readLeftIndex++];
    }
  }

  while (readLeftIndex < tmp.length()) {
    array[writeIndex++] = tmp[readLeftIndex++];
  }
}

Further optimizations would include allocating a single buffer of size array.length / 2 at the top level function and pass it around to avoid repeated allocations, but that would probably take away from readability, so am skipping it here.

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