Wrong inversions and duplicate numbers in MergeSort implementation in Java

Question

I'm creating a Java program in which I implement the MergeSort algorithm. My code is the following (so far):

public void merge(Integer [] left, Integer[] right, Integer[] a) {

    int i = 0;                  // a[] index (A)
    int lIndex = 0;             // left[] index (B)
    int rIndex = 0;             // right[] index (C)

    // Begin main merge process
    while((lIndex < left.length) && (rIndex < right.length)) {
        if(left[lIndex] <= right[rIndex]) {
            a[i] = left[lIndex]; // Store it
            lIndex++; // Increase index of left[]
        }
        else {
            a[i] = right[rIndex]; // Store it
            rIndex++; // Increase index of right[]
        }
        i++; // Increase index of a[]
    }
    if(i == lIndex) { // If the left array is sorted
        while(rIndex < right.length) { // Copy the contents of rhe right array to a[]
            a[i] = right[rIndex];
            i++;
            rIndex++;
        }
    }
    else { // If the right array is sorted
        while(lIndex < left.length) { // Copy the contents of the left array to a[]
            a[i] = left[lIndex];
            i++;
            lIndex++;
        }
    }
}

The problem is that every time I execute the function, the input array is returned partially sorted. I mean the majority of the elements are at their correct position but there are one or two that are placed wrong and also a couple of others that are duplicates of other elements! As I can't see what's really the problem, can anyone please help me? The implementation is a mini project for a lesson and I can't use int[ ] (let's say) instead of Integer[ ], in order to copy the contents of array A[ ] with the Arrays.copyOf() method. Thanks in advance and please forgive my syntax/spelling mistakes.

Note that the input array is always a power of 2 (2, 4, 8, 16 etc), so every time I divide by 2 to find the index of the middle element, I always get an even number.

Answer 1

From what I can tell, the problem is in your merge method, here:

if (i == lIndex) { // If the left array is sorted ...

i is not necessarily equal to lIndex when the left array is sorted. As a result, the final part of the merge is not always executed. The duplicate elements you're seeing are left over from the original array A in the positions that weren't overwritten because of this.

The correct condition is:

if (lIndex == left.length) { // If the left array is sorted ...

Answer 2

I think your problem is here:

if(i == lIndex)

The way to check if you've run out of elements in a list is this:

if (lIndex == left.length)

In other words, if you take some elements from the left and some from the right, even if you exhaust the left array first, i will NOT be equal to lIndex when you've exhausted the left array. It will be greater.