(c) (8 points) The standard mergesort algorithm divides the original array into
ID: 3756216 • Letter: #
Question
(c) (8 points) The standard mergesort algorithm divides the original array into two sub arrays. Suppose we have a variant of the mergesort algorithm (call it 3-way mergesort) where we instead divide the array into three sub-arrays, which we will need to recursively sort then merge (i) Write down the recurrence for 3way-mergesort (ii) Prove that the running time is O(n log). Show all your work and techniques (e.g. if you used a recurrence tree) in your proof (iii Show that the running-time in part ii) is asymptotically the same as the run- ning time of standard mergesort. In other words, formally prove that nlogn - O(n log2 n) by showing that the constants for this O-notation exist. (iv) What happens to the running-time if, instead of splitting the array into 3 sub- arrays, we decide to split it into n sub-arrays where n is the input size?Explanation / Answer
1)
public class MS3Way
{
public static void 3waymerge(Integer[] arr)
{ if (arr == null)
return;
Integer[] FirArr = new Integer[arr.length];
for (int i = 0; i < FirArr.length; i++)
firArr[i] = arr[i];
Rec3way(FirArr, 0, arr.length, arr);
for (int i = 0; i < FirArr.length; i++)
arr[i] = FirArr[i];
}
int low, int high, Integer[] destArray)
{
if (high - low < 2)
return;
int mid1 = low + ((high - low) / 3);
int mid2 = low + 2 * ((high - low) / 3) + 1;
Rec3way(destArray, low, mid1, arr);
Rec3way(destArray, mid1, mid2, arr);
Rec3way(destArray, mid2, high, arr);
merge(destArray, low, mid1, mid2, high, arr);
}
public static void merge(Integer[] arr, int low,
int mid1, int mid2, int high,
Integer[] destArray)
{
int i = low, j = mid1, k = mid2, l = low;
while ((i < mid1) && (j < mid2) && (k < high))
{
if (arr[i].compareTo(arr[j]) < 0)
{
if (arr[i].compareTo(arr[k]) < 0)
da[l++] = arr[i++];
else
da[l++] = arr[k++];
}
else
{
if (arr[j].compareTo(arr[k]) < 0)
da[l++] = arr[j++];
else
da[l++] = arr[k++];
}
}
while ((i < mid1) && (j < mid2))
{
if (arr[i].compareTo(arr[j]) < 0)
da[l++] = arr[i++];
else
da[l++] = arr[j++];
}
while ((j < mid2) && (k < high))
{
if (arr[j].compareTo(arr[k]) < 0)
da[l++] = arr[j++];
else
da[l++] = arr[k++];
}
while ((i < mid1) && (k < high))
{
if (arr[i].compareTo(arr[k]) < 0)
da[l++] = arr[i++];
else
da[l++] = arr[k++];
}
while (i < mid1)
da[l++] = arr[i++];
while (j < mid2)
da[l++] = arr[j++];
while (k < high)
da[l++] = arr[k++];
}
public static void main(String args[])
{
Integer[] data = new Integer[] {22,45,86,47,89,67,35,-2,56,79,24};
3waymerge(data);
System.out.println("After 3 way merge sort: ");
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
}
}
2)..3 way merge sort drdrcreases the no of passes so by using recurrence relation time complexity is T(n)=3T(n/3)+ O(n) = O(nlogn) with base 3.
III) the divide steps same time apart from size of array so the time complexity for 2 wayis same as of 3 way merge sort
iv) the running time decreases when we splits array into multiple parts.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.