Question

4. (15 points) Recall that in merge sort, we partitioned the array into two halves then recursively apply merge sort on those two halves. Suppose instead we partitioned the array into three parts. Write a threewayMergeSort(int list) that returns sorted version of list via apply merge sort on three partitions instead of two // ThreeWayMergeSort.java public class ThreeWayMergeSort f public int threewayMergeSort (int [] list) f (a) (10 points) Fill threewayMergeSort methood (b) (2 points) Write the runtime of threeway mergesort in recursive formula. c)(3 points) Then what is the above runtime?

Answer 1

a.

public class ThreeWayMergeSort
{
// sample values
int[] input = {26, 2, 34, 77, 10, 13, 1, 19, 58, 65};
int len = input.length;
public static void main(String args[])
{
int[] data = new int[len];
data = threewayMergeSort(input);
System.out.println("After sorting: ");
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + ", ");
}
  
public static int[] threewayMergeSort(int[] list)
{
// sort function
mergeSortThreeWayRec(list, 0, list.length);
// return this array
return list;
}
// performing the merge sort algorithm on the given array of values in the rangeof indices [low, high]. low is minimum index, high is maximum index.
  
public static void mergeSortThreeWayRec(int[] list, int low, int high)
{
// Splitting array into 3 parts
int mid1 = low + ((high - low) / 3);
int mid2 = low + 2 * ((high - low) / 3) + 1;
  
// Sorting 3 arrays recursively from
// 1. low to mid1
// 2. mid1 to mid2
// 3. mid2 to high
mergeSortThreeWayRec(list, low, mid1);
mergeSortThreeWayRec(list, mid1, mid2);
mergeSortThreeWayRec(list, mid2, high);
// Merging the sorted arrays
merge(list, low, mid1, mid2, high);
}
/* Merge the sorted ranges [low, mid1], [mid1,
mid2] and [mid2, high] mid1 is first midpoint
index in overall range to merge mid2 is second
midpoint index in overall range to merge
*/
public static void merge(int[] list, int low, int mid1, int mid2, int high)
{
//create a temporary destination array for storing the sorted values.
int[] destArray = new int[len];
int i = low, j = mid1, k = mid2, l = low;
/* choose smaller of the smallest in the three parts
int i is used for traversing till mid1 from low
int j is used to traverse from mid1 till mid2
int k is used to traverse from mid2 till high
int l is used for the destination array traversal from low value
*/
// this will happen until all the common length of the three parts are covered
while ((i < mid1) && (j < mid2) && (k < high))
{
if (list[i]<list[j])
{
if (list[i]<list[k])
destArray[l++] = list[i++];
else
destArray[l++] = list[k++];
}
else
{
if (list[j]<list[k])
destArray[l++] = list[j++];
else
destArray[l++] = list[k++];
}
}
// case where first and second parts have remaining values
while ((i < mid1) && (j < mid2))
{
if (list[i]<(list[j])
destArray[l++] = list[i++];
else
destArray[l++] = list[j++];
}
// case where second and third parts have remaining values
while ((j < mid2) && (k < high))
{
if (list[j]<(list[k])
destArray[l++] = list[j++];
else
destArray[l++] = list[k++];
}
// case where first and third parts have remaining values
while ((i < mid1) && (k < high))
{
if (list[i]<(list[k])
destArray[l++] = list[i++];
else
destArray[l++] = list[k++];
}
// copy remaining values from the first part
while (i < mid1)
destArray[l++] = list[i++];
// copy remaining values from the second part
while (j < mid2)
destArray[l++] = list[j++];
// copy remaining values from the third part
while (k < high)
destArray[l++] = list[k++];
// copy all the elements to the initial list.
for(int z=0;z<len;z++)
list[z] = destArray[z];
}
}

b.

T(n) = T(n/3) + T(n/3) + T(n/3) + O(n)

1st T(n/3) is for time taken to solve the first 1/3rd part and the remaining are fro second 1/3rd part and last 1/3rd part respectively. O(n) is for merging the parts together.

Hence, T(n) = 3T(n/3) + O(n)

c.

From the above equation the runtime for 3-way merge sort is nlog₃n. You'll get this upon using the telescoping on the above recurrence relation.