Design and implement C/C++ Program to 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.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Merge function to merge two subarrays
void merge(long int arr[], long int left, long int mid, long int right) {
long int i, j, k;
long int n1 = mid - left + 1;
long int n2 = right - mid;
// Create temporary arrays
long int L[n1], R[n2];
// Copy data to temporary arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Merge the temporary arrays back into arr[left..right]
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Merge sort function
void mergeSort(long int arr[], long int left, long int right) {
if (left < right) {
// Find the middle point
long int mid = left + (right - left) / 2;
// Sort first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
// Driver code
int main() {
long int n = 10000;
int it = 0;
// Arrays to store time duration of sorting algorithms
double time[10];
printf("A_size, Merge\n");
// Perform 10 iterations
while (it++ < 10) {
long int a[n];
// Generating n random numbers and storing them in arrays a
for (int i = 0; i < n; i++) {
long int num = rand() % n + 1;
a[i] = num;
}
// Using clock_t to store time
clock_t start, end;
// Merge sort
start = clock();
mergeSort(a, 0, n - 1);
end = clock();
// Calculate the time taken for sorting
time[it] = ((double)(end - start)) / CLOCKS_PER_SEC;
// Print the size of the array and the time taken for sorting
printf("%li, %f\n", n, time[it]);
// Increase the size of array by 10000
n += 10000;
}
return 0;
}