Explain the sorting algorithm MergeSort, presented below, considering the example of a = {5, 3, 4, 7, 1, 2} while noting down all intermediate steps. Explain the principle of “divide and conquer” with this algorithm. // auxiliary function for recursive sorting by merging private static void _mergeSort(int a[], int copy[], int start, int end){ if (start < end) { int mid = (start + end) / 2; mergeSort(a, copy, start, mid); mergeSort(a, copy, mid + 1, end); merge(a, copy, start, mid, end); } } private static void merge(int a[], int copy[], int start, int m, int end) { int i = 0, j = start, k; while (j <= m) copy[i++] = a[j++]; i = 0; k = start; while (k < j && j <= end) { if (copy[i] <= a[j]) a[k++] = copy[i++]; else a[k++] = a[j++]; } while (k < j) a[k++] = copy[i++]; } public static void mergeSort(int[] a) { mergeSort(a, new int[a.length], 0, a.length - 1)\ } 2. Why does this algorithm require less space than that one presented during the lecture? 3. Is this MergeSort algorithm stable? Give reasons for your answer
Explain the sorting
{5, 3, 4, 7, 1, 2} while noting down all intermediate steps. Explain the principle of “divide
and conquer” with this algorithm.
// auxiliary function for recursive sorting by merging
private static void _mergeSort(int a[], int copy[], int start, int end){
if (start < end) {
int mid = (start + end) / 2;
mergeSort(a, copy, start, mid);
mergeSort(a, copy, mid + 1, end);
merge(a, copy, start, mid, end);
}
}
private static void merge(int a[], int copy[], int start, int m, int end) {
int i = 0, j = start, k;
while (j <= m)
copy[i++] = a[j++];
i = 0;
k = start;
while (k < j && j <= end) {
if (copy[i] <= a[j])
a[k++] = copy[i++];
else
a[k++] = a[j++];
}
while (k < j)
a[k++] = copy[i++];
}
public static void mergeSort(int[] a) {
mergeSort(a, new int[a.length], 0, a.length - 1)\
}
2. Why does this algorithm require less space than that one presented during the lecture?
3. Is this MergeSort algorithm stable? Give reasons for your answer.
Step by step
Solved in 2 steps with 4 images
