If we were to run the following program for the list = {20, 27, 65, 49, 25, 19, 29, 48, 37, 56, 45, 23, 18, 47, 19, 28}, how many times do we call mergeSort method? public static void mergeSort(int[] list) { if (list.length > 1) { int[] firstHalf = new int[list.length / 2]; System.arraycopy(list, 0, firstHalf, 0, list.length / 2); mergeSort(firstHalf); int[] secondHalf = new int[list.length - list.length / 2]; System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalf.length); mergeSort(secondHalf); merge(firstHalf, secondHalf, list); } } public static void merge(int[] list1, int[] list2, int[] temp) { int current1 = 0, current2 = 0, current3 = 0; 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++]; } }
If we were to run the following program for the list = {20, 27, 65, 49, 25, 19, 29, 48, 37, 56, 45, 23, 18, 47, 19, 28}, how many times do we call mergeSort method?
public static void mergeSort(int[] list) {
if (list.length > 1) {
int[] firstHalf = new int[list.length / 2];
System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
mergeSort(firstHalf);
int[] secondHalf = new int[list.length - list.length / 2];
System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalf.length);
mergeSort(secondHalf);
merge(firstHalf, secondHalf, list);
}
}
public static void merge(int[] list1, int[] list2, int[] temp) {
int current1 = 0, current2 = 0, current3 = 0;
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++];
}
}
Step by step
Solved in 3 steps
