Im having some trouble with my arrays with merge sorting. Every case I have, the merge works fine until it hits the recursive method and send a previously merged array back. Most cases it rearranges the arrays that were already sorted and messes up the second merge method. For example: (3)(2)(1)(4) -> (2,3)(1,4) -> (1,3,2,4) would be a probable result. What am I doing wrong that could be causing this?
public static int[] mergeSort(int[] numbers) {
if (numbers.length == 1) {
return numbers; }
int[] leftSide = new int[numbers.length/2];
int[] rightSide = new int[numbers.length-leftSide.length];
System.arraycopy(numbers,0,leftSide,0,leftSide.length);
System.arraycopy(numbers,leftSide.length,rightSide,0,rightSide.length);
mergeSort(leftSide);
mergeSort(rightSide);
displayArray(leftSide);
displayArray(rightSide);
numbers = merge(leftSide,rightSide);
System.out.println("=============");
return numbers;
}
public static int[] merge(int[] left, int[] right) {
int[] temp = new int[left.length+right.length];
int l = 0;
int r = 0;
int t = 0;
while (l < left.length && r < right.length) {
if (left[l] > right[r]) {
temp[t] = right[r];
r++;
t++; }
else {
temp[t] = left[l];
l++;
t++; }
}//while
while (l < left.length) {
temp[t] = left[l];
l++;
t++; }
while (r < right.length) {
temp[t] = right[r];
r++;
t++; }
displayArray(temp);
return temp;
}
The mergeSort function returns a sorted array, which we are not tracking. Since the sorted array(left & right) is lost, the merge function is again picking up unsorted left and right array. The fix would be to update
mergeSort(leftSide);
mergeSort(rightSide);
to
leftSide = mergeSort(leftSide);
rightSide = mergeSort(rightSide);
This will update them to their respective sorted values