3. Sort a given set of n integer elements using Merge Sort method and compute its time complexity. Run the program for varied values of n> 5000, and record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator. Demonstrate using C++/Java how the divide-and-conquer method works along with its time complexity analysis: worst case, average case and best case.
import java.util.*;
public class MergeSort {
public static void merge(int array[], int low, int mid, int high) {
int h = low, i = low, j = mid + 1;
int b[] = new int[array.length];
while (h <= mid && j <= high) {
if (array[h] <= array[j]) {
b[i++] = array[h++];
} else {
b[i++] = array[j++];
}
}
if (h > mid) {
for (int k = j; k <= high; k++) {
b[i++] = array[k];
}
} else {
for (int k = h; k <= mid; k++) {
b[i++] = array[k];
}
}
for (int k = low; k <= high; k++) {
array[k] = b[k];
}
}
public static void mergesort(int array[], int low, int high) {
if (low < high) {
int mid = (int) Math.floor((low + high) / 2);
mergesort(array, low, mid);
mergesort(array, mid + 1, high);
merge(array, low, mid, high);
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of n (n > 5000): ");
int n = scan.nextInt();
int arr[] = new int[n];
Random random = new Random();
for (int i = 0; i < n; i++) {
arr[i] = random.nextInt(100000);
}
System.out.println("Random Array: " + Arrays.toString(arr));
long start = System.nanoTime();
mergesort(arr, 0, arr.length - 1);
long end = System.nanoTime();
System.out.println("Sorted Array: " + Arrays.toString(arr));
System.out.println("Time taken to complete the process : " + (end - start) / 1e6 + " milli seconds");
}
}
NULL