Question

please help me with this question. This is required to be written in Java.

Objective The objective of this programming assignment is to design and implement in Java the Merge-Sort algorithm presented in the lecture to sort a list of numbers. We are interested in exploring the relationship between the time complexity and the "real time". For this exploration, you will collect the execution time T(n) as a function of n and plot the functions T(n)/log:(n). T(n)/n.log:(n), and T(n)/n2.loga(n) on the same graph. Finally, discuss your results. Program to implement collect Data () Generate an array G of HUGE length L (as huge as your language allows) with random values capped at 0xfffffffe. for n 1,000 to L (with step 1,000) copy in Array A n first values from Array G Start timing //We time the sorting of Array A of length n Merge-Sort (A, 0, n-1) Store the value n and the values T (n)/log2 (n), T(n) /n.log2 (n), and T (n)/n2.log2 (n) in a file F where T (n) is the execution time Data Analysis Use any plotting software (e.g. Excel) to plot the values T(n)/log:(n), T(n)/n.log:(n), and T(n)/n2.log:(n) in File F as a function of n. File F is the file produced by the program you implemented. Discuss your results based on the plots. (Hint: is T(n) closer to K. loga(n), K. n.loga(n), or K. n2.log:(n) where K is a constant?) Report Write a report that will contain, explain, and discuss the plot. The report should not exceed one page. In addition, your report must contain the following information: whether the program works or not (this must be just ONE sentence) othe directions to compile and execute your program Good writing is expected. Recall that answers must be well written, documented., justified, and presented to get full cr

Answer 1

Solution:

import java.util.Scanner;

import java.util.*;

import java.text.*;

class Main

{

void mergetech(int numarr[], int l, int m, int r)

{

//variable declaration

int t1 = m - l + 1;

int t2 = r - m;

int leftarr[] = new int [t1];

int rightarr[] = new int [t2];

for (int i=0; i<t1; ++i)

leftarr[i] = numarr[l + i];

for (int j=0; j<t2; ++j)

rightarr[j] = numarr[m + 1+ j];

int i = 0, j = 0;

int k = l;

while (i < t1 && j < t2)

{

if (leftarr[i] <= rightarr[j])

{

numarr[k] = leftarr[i];

i++;

}

else

{

numarr[k] = rightarr[j];

j++;

}

k++;

}

while (i < t1)

{

numarr[k] = leftarr[i];

i++;

k++;

}

while (j < t2)

{

numarr[k] = rightarr[j];

j++;

k++;

}

}

//sorting method

void sorting(int numarr[], int l, int r)

{

if (l < r)

{

int m = (l+r)/2;

sorting(numarr, l, m); //invoking the function

sorting(numarr , m+1, r);

mergetech(numarr, l, m, r);

}

}

static void display(int numarr[]) //display fuction

{

int n = numarr.length;

for (int i=0; i<n; ++i) //displaying the values

System.out.print(numarr[i] + " ");

System.out.println();

}

public static void main(String args[]) //main function

{

Scanner sc=new Scanner(System.in);

int i,n;

//start of execution time

long start = System.currentTimeMillis();

//accepting the length of the array

System.out.println("Enter the length of the array");

n=sc.nextInt();

int numarr[]= new int[n];

//accepting the elements of the array

System.out.println("Enter the elements of the array");

for(i=0;i<n;i++)

{

numarr[i]=sc.nextInt();

}

System.out.println("Before Sorting");

System.out.println("Input Array");

display(numarr);

Main ob = new Main(); //object of the array

ob.sorting(numarr, 0, n-1); //calling the sorting function

//end of execution time

long end = System.currentTimeMillis();

System.out.println("After Sorting");

System.out.println(" Output array");

display(numarr);

NumberFormat formatter = new DecimalFormat("#0.00000");

//displaying the execution time

System.out.print("Execution time is " + formatter.format((end - start) / 1000d) + " seconds");

}

}

OUTPUT

Enter the length of the array Enter the elements of the array 99 34 56 Before Sorting Input Array 99 34 2 56 1 After Sorting Output array 1 2 34 56 99 Execution time is 7.40100 seconds

Enter the length of the array 10 Enter the elements of the array 77 Before Sorting Input Array 99 67 34 1 2 44 65 33 31 77 After Sorting Output array 1 2 31 33 34 44 65 67 77 99 Execution time is 14.96700 seconds

Merge sort is a type of recursive algorithm
Hence
recurrence relation T(n)=2T(n/2) + Theta(n)

If we see this the merge sort always divides the array into two parts and then it takes time which is linear in account to join the arrays.
Hence the time complexity for both best ,average and worst case is same which is Theta(nLogn).