What's wrong with my merge sort implementation?

// merge operation for merge sort
private static void merge(int[] a, int left, int middle, int right) {
int[] temp = new int[right - left + 1];        
int leftCrawler = left, rightCrawler = middle;
int currentIndex = 0;
while (leftCrawler < middle && rightCrawler <= right) {
if (a[leftCrawler] < a[rightCrawler])
temp[currentIndex++] = a[leftCrawler++];
else
temp[currentIndex++] = a[rightCrawler++];
}
while (leftCrawler < middle)
temp[currentIndex++] = a[leftCrawler++];
while (rightCrawler <= right)
temp[currentIndex++] = a[rightCrawler++];
// copy temp into a
for (int i = 0; i < temp.length; i++)
a[i] = temp[i];
}
private static void mergeSort(int[] a, int left, int right) {
if (right > left) {
int middle = left + (right - left) / 2;
mergeSort(a, left, middle);
mergeSort(a, middle + 1, right);
merge(a, left, middle, right);
}
}
public static void mergeSort(int[] a) {
int left = 0, right = a.length - 1;
mergeSort(a, left, right);
}

So, I thought that the issue might be with my merge operation, however I tested it on the following array int[] a = {2, 5, 7, 15, 8, 9, 10} with left = 0, middle = 4 and right = a.length - 1 and the merge operation does what it needs to successfully.

I have compared my implementation of mergeSort to those on various websites and I can't spot a difference. My mergeSort will not successfully sort the array. What am I doing wrong?

The problem might be with your copy:

    // copy temp into a
    for(int i = 0; i < temp.length; i++)
        a[i] = temp[i];

What you probably want is (notice the left + i):

    // copy temp into a
    for(int i = 0; i < temp.length; i++)
        a[left + i] = temp[i];

(Your test did not detect the issue, since left was 0.)

There are 3 errors in your code:

• the merge loop does not include the element at a[middle] because you use leftCrawler < middle instead of:

    while (leftCrawler <= middle && rightCrawler <= right)
  

• the second loop while (leftCrawler < middle) must also be changed to:

    while (leftCrawler <= middle)
  

• the loop to copy from temp back to a uses an incorrect index into a. It should be:

        // copy temp into a
  for (int i = 0; i < temp.length; i++)
  a[left + i] = temp[i];
  

Note that the first error is rooted in the noxious convention used here where right and middle are included in the slices instead of excluded. Excluding the right boundaries allows for simpler code without any error prone +1/-1 adjustments.

Here is a modified version:

// merge operation for merge sort
private static void merge(int[] a, int left, int middle, int right) {
    int[] temp = new int[right - left];        
    int leftCrawler = left, rightCrawler = middle;
    int currentIndex = 0;

    while (leftCrawler < middle && rightCrawler < right) {
        if (a[leftCrawler] < a[rightCrawler])
            temp[currentIndex++] = a[leftCrawler++];
        else
            temp[currentIndex++] = a[rightCrawler++];
    }

    while (leftCrawler < middle)
        temp[currentIndex++] = a[leftCrawler++];

    while (rightCrawler < right)
        temp[currentIndex++] = a[rightCrawler++];

    // copy temp into a
    for (int i = 0; i < temp.length; i++)
        a[left + i] = temp[i];
}

private static void mergeSort(int[] a, int left, int right) {
    if (right - left >= 2) {
        int middle = left + (right - left) / 2;
        mergeSort(a, left, middle);
        mergeSort(a, middle, right);
        merge(a, left, middle, right);
    }
}

public static void mergeSort(int[] a) {
    mergeSort(a, 0, a.length);
}