Divide-and-Conquer A 3-way merge-sort is an algorithm to sort an array A, descri
ID: 641268 • Letter: D
Question
Divide-and-Conquer
A 3-way merge-sort is an algorithm to sort an array A, described as follows:
Divide: divide the array into three (about) equal sized subarrays A[p..q1], A[q1+1..q2] and A[q2+1..r]
Conquer: Recursively sort these three subarrays.
Combine: Call a procedure 3-way-merge(A, p, q1, q2, r) to merge three sorted subarrays to a sorted array (a)
Please write a recursive pseudocode for this algorithm. Assume the 3-way-merge procedure is available to be used (you can call it directly).
3-way-merge-sort(A, p, r) // A: the input array, p: starting index, r: ending index. {
}
(b)(4 points) Please write down the recurrence equation for this 3-way-merge-sort algorithm.
Explanation / Answer
public static void mergesort(int[] data) {
int elements = data.length;
int sizeLeft;
int sizeCenter;
int sizeRight;
if (elements > 2) {
if (elements % 3 == 0) {
sizeLeft = elements / 3;
sizeCenter = elements / 3;
sizeRight = elements / 3;
} else if (elements % 3 == 1) {
sizeLeft = (elements / 3) + 1;
sizeCenter = elements / 3;
sizeRight = elements / 3;
} else { //if (elements % 3 == 2)
sizeLeft = (elements / 3) + 1;
sizeCenter = elements / 3;
sizeRight = (elements / 3) + 1;
}
int[] left = makeArray(data, 0, sizeLeft);
int[] center = makeArray(data, sizeLeft, sizeCenter);
int[] right = makeArray(data, sizeLeft + sizeCenter, sizeRight);
mergesort(left);
mergesort(center);
mergesort(right);
merge(data, left, center, right);
}
}
public static void merge(int[] data, int[] left, int[] center, int[] right) {
int[] temp = new int[left.length + center.length + right.length];
int copiedTotal = 0;
int copiedLeft = 0;
int copiedCenter = 0;
int copiedRight = 0;
while ((copiedLeft < left.length)
&& (copiedCenter < center.length)
&& (copiedRight < right.length)) {
if ((left[copiedLeft] < center[copiedCenter])
&& (left[copiedLeft] < right[copiedRight])) {
temp[copiedTotal++] = left[(copiedLeft++)];
} else if ((center[copiedCenter] < left[copiedLeft])
&& (center[copiedCenter] < right[copiedRight])) {
temp[copiedTotal++] = center[copiedCenter++];
} else {
temp[copiedTotal++] = right[copiedRight++];
}
}
while ((copiedLeft < left.length) && (copiedCenter < center.length)) {
if (left[copiedLeft] < center[copiedCenter]) {
temp[copiedTotal++] = left[copiedLeft++];
} else{
temp[copiedTotal++] = center[copiedCenter++];
}
}
while ((copiedLeft < left.length) && (copiedRight < right.length)) {
if (left[copiedLeft] < right[copiedRight]) {
temp[copiedTotal++] = left[copiedLeft++];
} else{
temp[copiedTotal++] = right[copiedRight++];
}
}
while ((copiedCenter < center.length) && (copiedRight < right.length)) {
if (center[copiedCenter] < right[copiedRight]) {
temp[copiedTotal++] = center[copiedCenter++];
} else{
temp[copiedTotal++] = right[copiedRight++];
}
}
while (copiedLeft < left.length) {
temp[copiedTotal++] = left[copiedLeft++];
}
while (copiedCenter < center.length) {
temp[copiedTotal++] = center[copiedCenter++];
}
while (copiedRight < right.length) {
temp[copiedTotal++] = right[copiedRight++];
}
System.arraycopy(temp, 0, data, 0, left.length + center.length + right.length);
}
}