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.
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 ...