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.

 #include <stdio.h>

#include <stdlib.h>

#include <time.h>

// Function to merge two subarrays

void merge(int arr[], int left, int mid, int right) {

    int i, j, k;

    int n1 = mid - left + 1;

    int n2 = right - mid;

    int L[n1], R[n2];

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

        L[i] = arr[left + i];

    for (j = 0; j < n2; j++)

        R[j] = arr[mid + 1 + j];

    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++;

    }

    while (i < n1) {

        arr[k] = L[i];

        i++;

        k++;

    }

    while (j < n2) {

        arr[k] = R[j];

        j++;

        k++;

    }

}

// Merge Sort function

void mergeSort(int arr[], int left, int right) {

    if (left < right) {

        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);

        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);

    }

}

int main() {

    int n;

    printf("Enter number of elements (n > 5000): ");

    scanf("%d", &n);

    if (n <= 5000) {

        printf("Please enter n greater than 5000.\n");

        return 1;

    }

    int *arr = (int *)malloc(n * sizeof(int));

    if (arr == NULL) {

        printf("Memory allocation failed.\n");

        return 1;

    }

    // Generating random numbers

    srand(time(0));

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

        arr[i] = rand() % 100000; // Random numbers between 0 and 99999

    }

    clock_t start, end;

    double cpu_time_used;

    start = clock();

    mergeSort(arr, 0, n - 1);

    end = clock();

    cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

    printf("Time taken to sort %d elements: %f seconds\n", n, cpu_time_used);

    free(arr);

    return 0;

}