Directions: Implement a recursive version of merge sort and a merge “helper” met
ID: 3815786 • Letter: D
Question
Directions:
Implement a recursive version of merge sort and a merge “helper” method. Add functionality to your code to count the total number of times all loops in your merge method execute and display this number when the sort is finished. Call your recursive merge sort algorithm with four different arrays: a 10 item array that is the best case for the algorithm, a 10 item array that is the worst case for the algorithm, a 100 item array that is the best case for the algorithm, and a 100 item array that is the worst case for the algorithm.
Note: you will not receive credit if your implementation does not count the number of iterations that are done by loops in your merge. It is ok to do this count as a global variable.
Hint: Since the best and worst case time complexity of merge sort is the same, the number of iterations for the best and worst case of each array size should be equal.
Example:
int[] test1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
System.out.println(Arrays.toString(mergeSort(test1)));
System.out.println(iterations + " iterations”);
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
34 iterations
Explanation / Answer
HI, Please find my implementation.
I have test with two test case : 10 elemets with best case and worst case.
You can test with 100 numbers.
Please let me know in case of any issue.
import java.util.Arrays;
/* Java program for Merge Sort */
public class MergeSort
{
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
private static int count = 0; // to count the number of iteration
public static void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i){
L[i] = arr[l + i];
//count++;
}
for (int j=0; j<n2; ++j){
R[j] = arr[m + 1+ j];
//count++;
}
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
count++;
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
count++;
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of L[] if any */
while (j < n2)
{
count++;
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
public static void sort(int arr[], int l, int r)
{
if (l < r)
{
// Find the middle point
int m = (l+r)/2;
// Sort first and second halves
sort(arr, l, m);
sort(arr , m+1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
// Driver method
public static void main(String args[])
{
int[] test1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
System.out.println("Given Array");
System.out.println(Arrays.toString(test1));
sort(test1, 0, test1.length-1);
System.out.println("Sorted array");
System.out.println(Arrays.toString(test1));
System.out.println("Iterations: "+MergeSort.count);
// setting count to 0
MergeSort.count = 0;
System.out.println(" ");
int[] test2 = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
System.out.println("Given Array");
System.out.println(Arrays.toString(test2));
sort(test1, 0, test2.length-1);
System.out.println("Sorted array");
System.out.println(Arrays.toString(test2));
System.out.println("Iterations: "+MergeSort.count);
}
}
/*
Sample run:
Given Array
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Sorted array
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Iterations: 34
Given Array
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Sorted array
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Iterations: 34
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.