I'm writing my own mergeSort method from scratch for a CS course, but somewhere a long the way it seems to lose it's way...
public static int[] mergeSort(int[] array) { if (array.length <= 1){ return array; } int[] left; int[] right; if (array.length%2 == 1){ left = new int[array.length/2+1]; }else { left = new int[array.length/2]; } right = new int[array.length/2]; System.arraycopy(array, 0, left, 0, left.length); System.arraycopy(array, left.length, right, 0, right.length); mergeSort(left); System.out.println("A left value returned with result: " + printArray(left)); mergeSort(right); System.out.println("A right value returned with result: " + printArray(right)); //printArray(merge(left, right)); return merge(left, right); } public static int[] merge(int[] left, int[] right) { int[] result = new int[left.length+right.length]; int count = 0; while (left.length > 0 || right.length >0) { if (left.length > 0 && right.length > 0) { if (left[0] <= right[0]){ System.out.println("Left most of " + printArray(left) + " is less than left most of " +printArray(right)); result[count] = left[0]; left = helperFunction(left); } else { System.out.println("Left most of " + printArray(right) + " is less than left most of " +printArray(left)); result[count] = right[0]; right = helperFunction(right); } } else if (left.length > 0) { System.out.println("Left most of " + printArray(left) + " is the next to add."); result[count] = left[0]; left = helperFunction(left); } else if (right.length > 0) { System.out.println("Left most of " + printArray(right) + " is the next to add."); result[count] = right[0]; right = helperFunction(right); } count++; } System.out.println("The result is: "+printArray(result)); return result; } public static int[] helperFunction(int[] array) { int[] helperArray; helperArray = new int[array.length-1]; System.arraycopy(array, 1, helperArray, 0, array.length-1); return helperArray; } public static String printArray(int[] array) { String result = "["; for(int i=0;i<array.length;i++){ result += (array[i]); if (i!=array.length-1){ result += ", "; } } result += "]"; return result; }
Those are the methods I'm using. helperMethod just removes the first element of an array, the printArray method is there for testing purposes, along with the extensive amount of line printing.
When I call mergeSort on the array {3, 2, 1} the out put is:
If you take a look at the lines in red, I call printArray on the "result" right before I return it and it's fine and sorted. Then after it's been returned to mergeSort, I have a println that should in theory be printing the same array, but it's been flipped.[3, 2, 1]
A left value returned with result: [3]
A right value returned with result: [2]
Left most of [2] is less than left most of [3]
Left most of [3] is the next to add.
The result is: [2, 3]
A left value returned with result: [3, 2]
A right value returned with result: [1]
Left most of [1] is less than left most of [3, 2]
Left most of [3, 2] is the next to add.
Left most of [2] is the next to add.
The result is: [1, 3, 2]
What gives?
If anyone can explain what's going on I would greatly appreciate it.