Combine wrong output
I am having two problems with my merge sort code in Java.
-
When I enter the array [3,4,2,1,0,6,8], I get the output [0, 1, 2, 3, 4, 6, 0], which is clearly not true.
-
I suspect that the way I wrote my code is not as optimal as it could be. Please let me know if you can find any improvements. I know there are many merge algorithms on the internet, but I am asking specifically about how I wrote my code. Thank!
import java.util.Arrays; public class Main { static int[] mergeSort(int[] arr) { if (arr == null) return null; if (arr.length <= 1) return arr; int length = arr.length; int mid = arr.length / 2; int[] left = Arrays.copyOfRange(arr, 0, mid); int[] right = Arrays.copyOfRange(arr, mid, length); int[] sortedLeft = mergeSort(left); int[] sortedRight = mergeSort(right); int leftSmallestIndex = 0; int rightSmallestIndex = 0; int leftLength = left.length; int rightLength = right.length; int[] sortedArr = new int[length]; outer: for (int i = 0; i < length; i++) { if (leftSmallestIndex >= leftLength) { while (rightSmallestIndex < rightLength) { sortedArr[i] = sortedRight[rightSmallestIndex]; rightSmallestIndex++; break outer; } } if (rightSmallestIndex >= rightLength) { while (leftSmallestIndex < leftLength) { sortedArr[i] = sortedLeft[leftSmallestIndex]; leftSmallestIndex++; break outer; } } if (sortedLeft[leftSmallestIndex] < sortedRight[rightSmallestIndex]) { sortedArr[i] = sortedLeft[leftSmallestIndex]; leftSmallestIndex++; } else { sortedArr[i] = sortedRight[rightSmallestIndex]; rightSmallestIndex++; } } return sortedArr; } public static void main(String[] args) { // write your code here int[] a = new int[] {3,4,2,1,0,6,8}; System.out.println(Arrays.toString(mergeSort(a))); } }
source to share
Your statement break outer;
actually forces the control to exit the for loop, it does not continue the for loop (I am assuming you are trying to continue the for loop using this statement break outer;
).
This forces the loop to update only one remaining element from sortedRight
or sortedLeft
to get into the sorted array and the rest are skipped, this calls 0
at the end of your loop.
You don't actually need to do this, you can loop to - leftSmallestIndex < leftLength && rightSmallestIndex < rightLength
and then execute the while loops you defined inside the for loop, outside of it.
Example -
import java.util.*;
import java.math.*;
class a {
static int[] mergeSort(int[] arr) {
if (arr == null)
return null;
if (arr.length <= 1)
return arr;
int length = arr.length;
int mid = length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, length);
int[] sortedLeft = mergeSort(left);
int[] sortedRight = mergeSort(right);
int leftSmallestIndex = 0;
int rightSmallestIndex = 0;
int leftLength = left.length;
int rightLength = right.length;
int[] sortedArr = new int[length];
int i = 0;
for (; leftSmallestIndex < leftLength && rightSmallestIndex < rightLength;i++) {
if (sortedLeft[leftSmallestIndex] < sortedRight[rightSmallestIndex]) {
sortedArr[i] = sortedLeft[leftSmallestIndex];
leftSmallestIndex++;
}
else {
sortedArr[i] = sortedRight[rightSmallestIndex];
rightSmallestIndex++;
}
}
while (rightSmallestIndex < rightLength) {
sortedArr[i] = sortedRight[rightSmallestIndex];
rightSmallestIndex++;
i++;
}
while (leftSmallestIndex < leftLength) {
sortedArr[i] = sortedLeft[leftSmallestIndex];
leftSmallestIndex++;
i++;
}
return sortedArr;
}
public static void main(String[] args) {
int[] a = new int[] {3,4,2,1,0,6,8};
System.out.println(Arrays.toString(mergeSort(a)));
outer : for(int i = 0;i < 10 ; i++) {
while(true) {
System.out.println(i);
break outer;
}
}
}
}
I added an example at the end (a simple version of what you were trying to use break outer;
, this should help you figure out what's going on).
source to share
Your problem is in the while loop:
while (rightSmallestIndex < rightLength) {
sortedArr[i] = sortedRight[rightSmallestIndex];
rightSmallestIndex++;
break outer;
}
will never loop because your break statement is INSIDE while. Also, you don't increment i
inside while, so even if it loops, it will overwrite the values at the current index instead of filling the rest of the array
Changing them to
if (leftSmallestIndex >= leftLength) {
while (rightSmallestIndex < rightLength) {
sortedArr[i] = sortedRight[rightSmallestIndex];
rightSmallestIndex++;
i++;
}
break outer;
}
if (rightSmallestIndex >= rightLength) {
while (leftSmallestIndex < leftLength) {
sortedArr[i] = sortedLeft[leftSmallestIndex];
i++;
leftSmallestIndex++;
}
break outer;
}
..rest is the same
Should give correct results
As for the improvements ...
-
do not use labels and expressions
break LABEL
, it confuses it very much, perhaps it is clearer to refactor these parts into their own methods with specifying method identifiers likefillInRemainingArray()
-
I don't think you need to make copies of the array, you should be able to concatenate with just one array
source to share