mergesort

 #include <stdio.h>

#include <stdlib.h>

#include <time.h>

void merge(int arr[], int l, int m, int r) {

    int i, j, k;

    int n1 = m - l + 1;

    int n2 = r - m;

    int* L = (int*)malloc(n1 * sizeof(int));

    int* R = (int*)malloc(n2 * sizeof(int));

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

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

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

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

    i = 0;

    j = 0;

    k = l;

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

    }

    free(L);

    free(R);

}

void mergeSort(int arr[], int l, int r) {

    if (l < r) {

        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);

        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);

    }

}

int main() {

    int n, i;

    clock_t start, end;

    double cpu_time_used;

    printf("Enter the number of elements (n): ");

    scanf("%d", &n);

    if (n < 5000) {

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

        return 1;

    }

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

    if (arr == NULL) {

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

        return 1;

    }

    srand(time(NULL));

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

        arr[i] = rand() % 10000;

    }

    start = clock();

    mergeSort(arr, 0, n - 1);

    end = clock();

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

    printf("Time taken for sorting: %lf seconds\n", cpu_time_used);

    free(arr);

    return 0;

}