Merge Sort an integer array

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={

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

StackExchange Code Review Q#64711, answer score: 13