At the point where you merge l
and r
back in to nums
, have l
and r
been sorted yet?
Quick MergeSort troubleshooting [closed]
Вопрос
I've been trying get my Mergesort method to work, but it's giving me some funky outputs.
// mergesort method
// recursively sorts the array by breaking into small sub-arrays and then merging
public static int[] mergeSort(int[] nums){
int halfwayAndOne = (nums.length / 2);
int a = 0, b = 0;
if (nums.length <= 1)
return nums;
else{
int[] l = new int[nums.length / 2];
int[] r = new int[nums.length - l.length];
for (int i = 0; i < l.length; i++)
l[i] = nums[i];
for (int j = 0; j < nums.length - l.length; j++){
r[j] = nums[halfwayAndOne];
halfwayAndOne++;
}
for (int n = 0; n < nums.length; n++){
if (a < l.length && b < r.length) {
if (l[a] < r[b]) {
nums[n] = l[a];
a++;
} else {
nums[n] = r[b];
b++;
}
}
else if (a == l.length)
nums[n] = r[b];
else
nums[n] = l[a];
}
mergeSort(l);
mergeSort(r);
printArr(l);
printArr(r);
return nums;
}
}
// method to print out the array
public static void printArr(int[] arr){
System.out.println(Arrays.toString(arr));
}
This is the output:
[4, 0, 10, 15, 2, 1, 8, 9, 20, 3, 5]
[4]
[0]
[15]
[2]
[10]
[2, 15]
[0, 4]
[10, 15, 15]
[8]
[9]
[1]
[8, 9]
[3]
[5]
[20]
[3, 5]
[1, 8, 8]
[3, 5, 20]
[4, 0, 10, 10, 10]
[1, 8, 9, 20, 20, 20]
[1, 4, 0, 8, 9, 10, 15, 2, 20, 20, 20]
The first array is the original array, and the output should be sorted from least to greatest
Edit: My question is where is my program not working, thought it was self explanatory, sorry.
Решение
Не связан с StackOverflow