Java Merge Sort

Question

I implemented a merge sort in Java. Is there any way to improve it? I suspect that in particular the merging part could be improved.

Note: I deliberately removed all the comments.

private static void mergeSort(int[] values) {
   if (values.length < 2) {
      return;
   }

   int middle = values.length / 2;
   int leftSize = middle;
   int rightSize = values.length - middle;

   int[] left = new int[leftSize];
   int[] right = new int[rightSize];

   for (int i = 0; i < leftSize; i++) {
      left[i] = values[i];
   }

   for (int i = middle; i < values.length; i++) {
      right[i - middle] = values[i];
   }

   mergeSort(left);
   mergeSort(right);
   merge(left, right, values);
}

private static void merge(int[] left, int[] right, int[] values) {
   int leftPosition = 0;
   int rightPosition = 0;
   int position = 0;

   while (leftPosition < left.length && rightPosition < right.length) {
      if (left[leftPosition] <= right[rightPosition]) {
         values[position++] = left[leftPosition++];
      } else {
         values[position++] = right[rightPosition++];
      }
   }

   while (leftPosition < left.length) {
      values[position++] = left[leftPosition++];
   }
   while (rightPosition < right.length) {
      values[position++] = right[rightPosition++];
   }
}

Answer 1

Arrays.copyOf

   int middle = values.length / 2;
   int leftSize = middle;
   int rightSize = values.length - middle;

   int[] left = new int[leftSize];
   int[] right = new int[rightSize];

   for (int i = 0; i < leftSize; i++) {
      left[i] = values[i];
   }

You can rewrite everything but the right declaration as

   int[] left = Arrays.copyOf(values, values.length / 2);

That will declare a new array and copy the values, so no more manual traversing. Also, it may have a more optimized copy method.

Arrays.copyOfRange

   for (int i = middle; i < values.length; i++) {
      right[i - middle] = values[i];
   }

Taking the declaration of right from the previous code, we can write

   int[] right = Arrays.copyOfRange(values, left.length, values.length);

Again, the new array is created and copied in combination.

Combined, this gets us from fourteen lines to two, cutting the overall method length in half. Even if you put back middle as more self commenting, we're still considerably shorter.

System.arraycopy

   while (leftPosition < left.length) {
      values[position++] = left[leftPosition++];
   }
   while (rightPosition < right.length) {
      values[position++] = right[rightPosition++];
   }

There's a built-in for this as well.

   int remaining = left.length - leftPosition;
   if (remaining > 0) {
      System.arraycopy(left, leftPosition, values, position, remaining);
   } else {
      remaining = right.length - rightPosition;
      if (remaining > 0) {
         System.arraycopy(right, rightPosition, values, position, remaining);
      }
   }

It will just copy without creating a new array. The two cases are mutually exclusive, so switching from the while to if lets us add an else.

A possible optimization

If you're really desperate to improve performance and need to use this rather than Arrays.sort, you can try changing

   while (leftPosition < left.length && rightPosition < right.length) {
      if (left[leftPosition] <= right[rightPosition]) {
         values[position++] = left[leftPosition++];
      } else {
         values[position++] = right[rightPosition++];
      }
   }

to something like

   merging:
   while (true) {
      if (left[leftPosition] <= right[rightPosition]) {
         do {
            values[position++] = left[leftPosition++];
            if (leftPosition >= left.length) {
               break merging;
            }
         } while (left[leftPosition] <= right[rightPosition]);
      }

      do {
         values[position++] = right[rightPosition++];
         if (rightPosition >= right.length) {
            break merging;
         }
      } while (left[leftPosition] > right[rightPosition]);
   }

This is certainly less readable, but it might be faster. You'd have to benchmark it to see. The argument in favor of it being faster is that the original has to do three comparisons before copying an element. This only does one on the first iteration and two thereafter until the inner loops run out and it starts over.

You might be able to do even better by not copying immediately and instead waiting until you know how much to copy. Then you could use System.arraycopy.

Using break with the labelled outer loop is less readable in and of itself, but it is probably the fastest way to get this functionality.

If we broke it up into two loops, we could move the first if out of the loop.

   if (left[leftPosition] <= right[rightPosition]) {
      merging1:
      while (true) {
         do {
            values[position++] = left[leftPosition++];
            if (leftPosition >= left.length) {
               break merging1;
            }
         } while (left[leftPosition] <= right[rightPosition]);

         do {
            values[position++] = right[rightPosition++];
            if (rightPosition >= right.length) {
               break merging1;
            }
         } while (left[leftPosition] > right[rightPosition]);
      }
   } else {
      merging2:
      while (true) {
         do {
            values[position++] = right[rightPosition++];
            if (rightPosition >= right.length) {
               break merging2;
            }
         } while (left[leftPosition] > right[rightPosition]);

         do {
            values[position++] = left[leftPosition++];
            if (leftPosition >= left.length) {
               break merging2;
            }
         } while (left[leftPosition] <= right[rightPosition]);
      }
   }

More optimized but more duplicate code. Benchmark to make sure that this doesn't bypass a better compiler optimization.

Saving memory

This is \$\mathcal{O}(n \log n)\$ in memory. You keep having to allocate new temporary arrays. We can achieve linear memory just by creating one scratch array first. We can minimize the copies by switching between the scratch array and the original array. See an example solution here if you want more information.

Not only does this save memory, but reducing the number of memory allocations will reduce the time as well. Memory allocations are slow. This also reduces the number of copy operations that need to be done.

Mergesort is not efficient on small inputs

This uses mergesort all the way down to two element arrays. That's not necessary. Consider instead using a simpler method for small inputs. For example, insertion sort has low overhead and can be done in-place. Again, benchmark to find the optimal switching point.