Write a recursive version of this code. one in which n is divided by two. public static > void MergeSorting(T[] arr) { T[] tep = (T[]) new Comparable[arr.length]; MergeSorting(arr, tep, 0, arr.length - 1); } //Recursive helper method for the merge sort algorithm. //arr The array to sort //tep Temporary array for merge operation //start Index of the left end of the region to sort //end Index of the right end of the region to sort. private static > void mergeSort(T[] arr, T[] tep, int start, int end) { if (start >= end) { return; } int middle = (left + right) / 2; MergeSorting(arr, tep, start, middle); // first half MergeSorting(arr, tep, middle + 1, end); //second half Merge(arr, tep, start, middle, end); } private static > void Merge(T[] arr, T[] tep, int start, int middle, int end) { for (int i = start; i <= end; i++) { tep[i] = arr[i];//adds the arry to tep } int a = 0; int b = middle + 1; for (int current = start; current <= end; current++) { if (a == middle + 1) { arr[current] = tep[b++]; } else if (b > end) { arr[current] = tep[a++]; } else if (tep[a].compareTo(tep[b]) <= 0) { arr[current] = tep[a++]; } else { arr[current] = tep[b++]; } } } }
Write a recursive version of this code. one in which n is divided by two.
public static <T extends Comparable<T>> void MergeSorting(T[] arr) {
T[] tep = (T[]) new Comparable[arr.length];
MergeSorting(arr, tep, 0, arr.length - 1);
}
//Recursive helper method for the merge sort
//arr The array to sort
//tep Temporary array for merge operation
//start Index of the left end of the region to sort
//end Index of the right end of the region to sort.
private static <T extends Comparable<T>> void mergeSort(T[] arr, T[] tep, int start,
int end) {
if (start >= end) {
return;
}
int middle = (left + right) / 2;
MergeSorting(arr, tep, start, middle); // first half
MergeSorting(arr, tep, middle + 1, end); //second half
Merge(arr, tep, start, middle, end);
}
private static <T extends Comparable<T>> void Merge(T[] arr, T[] tep, int start, int middle,
int end) {
for (int i = start; i <= end; i++) {
tep[i] = arr[i];//adds the arry to tep
}
int a = 0;
int b = middle + 1;
for (int current = start; current <= end; current++) {
if (a == middle + 1) {
arr[current] = tep[b++];
} else if (b > end) {
arr[current] = tep[a++];
} else if (tep[a].compareTo(tep[b]) <= 0) {
arr[current] = tep[a++];
} else {
arr[current] = tep[b++];
}
}
}
}
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 7 images
