Merge Sort an integer array

Question

I've implemented merge sort an integer array. Is it okay to use i,j,k as variable name for looping? Should I change them to more meaningful names? Overall, any further suggestions on this code?

MergeSort.java

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {

    }

    public static void mergeSort(int[] inputArray) {
        int size = inputArray.length;
        if (size < 2)
            return;
        int mid = size / 2;
        int leftSize = mid;
        int rightSize = size - mid;
        int[] left = new int[leftSize];
        int[] right = new int[rightSize];
        for (int i = 0; i < mid; i++) {
            left[i] = inputArray[i];

        }
        for (int i = mid; i < size; i++) {
            right[i - mid] = inputArray[i];
        }
        mergeSort(left);
        mergeSort(right);
        merge(left, right, inputArray);
    }

    public static void merge(int[] left, int[] right, int[] arr) {
        int leftSize = left.length;
        int rightSize = right.length;
        int i = 0, j = 0, k = 0;
        while (i < leftSize && j < rightSize) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i++;
                k++;
            } else {
                arr[k] = right[j];
                k++;
                j++;
            }
        }
        while (i < leftSize) {
            arr[k] = left[i];
            k++;
            i++;
        }
        while (j < leftSize) {
            arr[k] = right[j];
            k++;
            j++;
        }
    }
}

MergeSortTest.java

import static org.junit.Assert.*;

import java.util.Arrays;

import org.junit.Test;

public class MergeSortTest {

    @Test
    public void reverseInput(){
        int[] arr={22,21,19,18,15,14,9,7,5};
        MergeSort.mergeSort(arr);
        assertEquals("[5, 7, 9, 14, 15, 18, 19, 21, 22]", Arrays.toString(arr));

    }
    @Test
    public void emptyInput(){
        int[] arr={};
        MergeSort.mergeSort(arr);
        assertEquals("[]", Arrays.toString(arr));
    }

    @Test
    public void alreadySorted(){
        int[] arr={1,2,3,4,5,6,7,8,9,10};
        MergeSort.mergeSort(arr);
        assertEquals("[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]", Arrays.toString(arr));
    }

}

Answer 1

Overall I would have to say that this is the neatest and most clear implementation of a Merge Sort that I have seen. There is nothing wrong with variables i, j and k. They are standard names for looped array indexes. There is a single empty line in your code which is inconsistent with the rest of the method. That is the only nitpick I can find in terms of the style and neatness. It is a tiny, inconsequential thing.

The only recommendations I can make, are things that will improve performance, or will introduce some other common practices that may impact readability, though they are still more standard than what you have.

First, some common practice things

• Consider doing post-increments inside the array-reference. This code:

  while (i < leftSize && j < rightSize) {
      if (left[i] <= right[j]) {
          arr[k] = left[i];
          i++;
          k++;
      } else {
          arr[k] = right[j];
          k++;
          j++;
      }
  }
  while (i < leftSize) {
      arr[k] = left[i];
      k++;
      i++;
  }
  while (j < leftSize) {
      arr[k] = right[j];
      k++;
      j++;
  }
  

  would commonly be written as:

  while (i < leftSize && j < rightSize) {
      if (left[i] <= right[j]) {
          arr[k++] = left[i++];
      } else {
          arr[k++] = right[j++];
      }
  }
  while (i < leftSize) {
      arr[k++] = left[i++];
  }
  while (j < leftSize) {
      arr[k++] = right[j++];
  }
  

  There is no change to the logic, the code is just a bit more compressed. The impact to readability is debatable, you get more code on a screen, but you have to look for the increments.

• You copy the array contents using a regular loop:

  int[] left = new int[leftSize];
  int[] right = new int[rightSize];
  for (int i = 0; i < mid; i++) {
      left[i] = inputArray[i];
  
  }
  for (int i = mid; i < size; i++) {
      right[i - mid] = inputArray[i];
  }
  

  The above would typically be done (for performance reasons), as one of two ways, either:

  int[] left = new int[leftSize];
  int[] right = new int[rightSize];
  System.arraycopy(inputArray, 0, left, 0, leftSize);
  System.arraycopy(inputArray, leftSize, right, 0, rightSize);
  

  In Java6 and above, the Arrays utility class can be used too:

  int[] left = Arrays.copyOfRange(inputArray, 0, leftSize);
  int[] right = Arrays.copyOfRange(inputArray, leftSize, inputArray.length);
  

  I would go with the Arrays.copyOfRange(...) call.

The above changes do not change the logic of your program at all, just the techniques used at the various points.

Your implementation would still be 'textbook'.

In terms of performance, though, your limit is the number of times you create, copy, and discard arrays of data.

There is a variant of the Merge Sort that uses just two arrays, the input array, and a 'temp' array that is the same size. The algorithm repeatedly merges small chunks of data from one array, to the other, then swaps them, and merges the now larger chunks back to the first, and keeps doing that until the data is sorted.

Using that algorithm means there is no additional array copying, etc. It is much faster, but the implementation would look very different to yours. Still I would recommend you try it. There are examples on Wikipedia

Answer 2

Note that the code would go wrong with odd number for the array length with duplicate values for example {1, 3, 15, 3, 7, 9, 8, 15, 0}. I think the problem is in:

while (i < leftSize) {
    arr[k] = left[i];
    k++;
    i++;
}
while (j < leftSize) {
    arr[k] = right[j];
    k++;
    j++;
}

The condition in the last loop should be on rightSize instead of leftSize:

while (i < leftSize) {
    arr[k++] = left[i++];
}
while (j < rightSize) {
    arr[k++] = right[j++];
}

Answer 3

Is it okay to use i,j,k as variable name for looping?

Sometimes... and often it's the best, e.g., in matrix multiplication there are three nested loops and no better names than i, j, k.

Should I change them to more meaningful names?

Can you find some? Descriptive and not too long. Is there a book/site/whatever using the same names? If so, then a link could help.

public static void main(String[] args) {

}

What the ...? This looks like the fastest sort ever!

int leftSize = left.length;

Not necessary on a normal JVM, probably useful on Android. Is it length or size? :D

merge could use some comments. Splitting it into two or more well named methods would be even better, but you'd have to pass too many variables... not really good.

Either I'm blind or this is a nice code!

However, the testing is pretty insufficient. It gets more interesting with non-monotonic sequences and what else... You could carefully design 20+ test cases and spend a whole day on it. :D

I'd recommend to do some pseudo-random testing instead. Fill an array with random ints, clone it, sort it, and evaluate. Either use Arrays#sort as the yardstick or verify some easily to prove properties: monotonicity and e.g. same sum as the original. Both is trivial to do, and running a few thousands tests takes less than one second.

Answer 4

There is a coding error in the above mentioned merge method code... The second third while loop should be limited by rightSize not leftSize

while (i < leftSize && j < rightSize) {
if (left[i] <= right[j]) {
    arr[k] = left[i];
    i++;
    k++;
} else {
    arr[k] = right[j];
    k++;
    j++;
}
}
while (i < leftSize) {
    arr[k] = left[i];
    k++;
    i++;
}
while (j < leftSize) {
    arr[k] = right[j];
    k++;
    j++;
}

It has to be corrected as

while (i < leftSize && j < rightSize) {
if (left[i] <= right[j]) {
    arr[k] = left[i];
    i++;
    k++;
} else {
    arr[k] = right[j];
    k++;
    j++;
}
}
while (i < leftSize) {
    arr[k] = left[i];
    k++;
    i++;
}
while (j < rightSize) {
    arr[k] = right[j];
    k++;
    j++;
}