#include <stdio.h>

#include <stdlib.h>

#include <time.h>

void merge(int arr[], int beg, int mid, int end);

void mergesort(int arr[], int beg, int end);

int main() {

    int arr[100], n = 100, i;

    // Generating random numbers

    int l = 1, u = 100, c = 100, A[100];

    int num;

    srand(time(0));

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

        num = (rand() % (u - l + 1)) + l;

        A[i] = num;

    }

    printf("Before sorting array is:\n");

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

        printf("%d\n", A[i]);

    }

    // Sorting using merge sort

    mergesort(A, 0, n - 1);

    printf("After sorting array is:\n");

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

        printf("%d\n", A[i]);

    }

    // Measuring execution time

    clock_t t;

    double tot_exec_time;

    t = clock();

    // Place the code whose execution time you want to measure here

    t = clock() - t;

    tot_exec_time = ((double)t) / CLOCKS_PER_SEC;

    printf("TOTAL TIME: %f\n", tot_exec_time);

    return 0;

}

void mergesort(int arr[], int beg, int end) {

    if (beg < end) {

        int mid = (beg + end) / 2;

        mergesort(arr, beg, mid);

        mergesort(arr, mid + 1, end);

        merge(arr, beg, mid, end);

    }

}

void merge(int arr[], int beg, int mid, int end) {

    int i, k, j;

    int n1 = mid - beg + 1;

    int n2 = end - mid;

    int leftarr[n1], rightarr[n2];

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

        leftarr[i] = arr[beg + i];

    }

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

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

    }

    i = 0;

    j = 0;

    k = beg;

    while (i < n1 && j < n2) {

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

            arr[k] = leftarr[i];

            i++;

        } else {

            arr[k] = rightarr[j];

            j++;

        }

        k++;

    }

    while (i < n1) {

        arr[k] = leftarr[i];

        i++;

        k++;

    }

    while (j < n2) {

        arr[k] = rightarr[j];

        j++;

        k++;

    }

}