public class MergeSort { // The method for sorting the numbers public static voi
ID: 3761086 • Letter: P
Question
public class MergeSort {
// The method for sorting the numbers
public static void mergeSort(int[] list) {
if (list.length > 1) {
// Merge sort the first half
int[] firstHalf = new int[list.length / 2];
System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
mergeSort(firstHalf);
// Merge sort the second half
int secondHalfLength = list.length - list.length / 2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);
// Merge firstHalf with secondHalf into list
merge(firstHalf, secondHalf, list);
}
}
// Merge two sorted lists
public static void merge(int[] list1, int[] list2, int[] temp) {
int current1 = 0; // Current index in list1
int current2 = 0; // Current index in list2
int current3 = 0; // Current index in temp
while (current1 < list1.length && current2 < list2.length) {
if(list1[current1] < list2[current2])
temp[current3++] = list1[current1++];
else temp[current3++] = list2[current2++];
}
while (current1 < list1.length)
temp[current3++] = list1[current1++];
while (current2 < list2.length)
temp[current3++] = list2[current2++];
}
public static void main(String[] args) {
// The test method
int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
mergeSort(list);
for(int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}
The question is: (Modify merge sort) Rewrite the mergeSort method to recursively sort the first half of the array and the second half of the array without creating new temporary arrays, and then merge the two into a temporary array and copy its contents to the original array, as shown in Figure 23.6b.
The image below is Figure 23.6b.
Explanation / Answer
public class MergeSort {
// The method for sorting the numbers
public static void mergeSort(int[] list) {
if (list.length > 1) {
// Merge sort the first half
int[] firstHalf = new int[list.length / 2];
System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
m_sort(firstHalf, temp, 0, array_size - 1);
//Implementing merge sort on first half of array recursively
void m_sort(int firstHalf[], int temp[], int left, int right) {
int mid;
if (right > left) {
mid = (right + left) / 2;
m_sort(firstHalf, temp, left, mid);
m_sort(firstHalf, temp, mid+1, right);
merge(firstHalf, temp, left, mid+1, right);
}
}
// Merge sort the second half
int secondHalfLength = list.length - list.length / 2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);
// Merge firstHalf with secondHalf into list
merge(firstHalf, secondHalf, list);
}
}
// Removing the temporary arrays from the code in second half
// Merge two sorted lists
public static void merge(int[] list1, int[] list2) {
int current1 = 0; // Current index in list1
int current2 = 0; // Current index in list2
while (current1 < list1.length && current2 < list2.length) {
if(list1[current1] < list2[current2]) {
list2[current2] = list2[current2] + list1[current1++];
list1[current1] = list2[current2] - list1[current1++];
list2[current2] = list2[current2] - list1[current1++];
}
else {
list2[current2] = list2[current2] + list1[current1++];
list1[current1] = list2[current2] - list1[current1++];
list2[current2] = list2[current2] - list1[current1++];
}
}
while (current1 < list1.length) {
list2[current2] = list2[current2] + list1[current1++];
list1[current1] = list2[current2] - list1[current1++];
list2[current2] = list2[current2] - list1[current1++];
}
while (current2 < list2.length) {
list2[current2] = list2[current2] + list1[current1++];
list1[current1] = list2[current2] - list1[current1++];
list2[current2] = list2[current2] - list1[current1++];
}
}
public static void main(String[] args) {
// The test method
int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
mergeSort(list);
for(int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.