#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
clock_t generate_data_timer, sorting_timer;


void merge(int* a, int n, int m) {
    int i, j, k;
    int* x = malloc(n * sizeof(int));
    for (i = 0, j = m, k = 0; k < n; k++) {
        x[k] = j == n ? a[i++]
            : i == m ? a[j++]
            : a[j] < a[i] ? a[j++]
            : a[i++];
    }
    for (i = 0; i < n; i++) {
        a[i] = x[i];
    }
    free(x);
}

void merge_sort(int *array, int array_length) {
    if (array_length < 2)
        return;
    int middle_index = array_length / 2;
    merge_sort(array, middle_index);
    merge_sort(array + middle_index, array_length - middle_index);
    merge(array, array_length, middle_index);
}

void print_array(int array[], int n) {
    for (int i = 0; i < n; ++i) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void generate_data(int A[], int N) {
    generate_data_timer = clock();
    int i;
    srand(10);
    for (i = 0; i < N; i++) {
        int a = A[i] = 10 + rand() % 1000;
    }
}

int main()
{
    int* a;
    int n;

    printf("Enter array length\n");
    scanf("%d", &n);

    a = (int*)malloc(n * sizeof(int));
    generate_data(a, n);

    printf("Before Merge Sort: ");
    print_array(a, n);

    sorting_timer = clock();

    merge_sort(a, n);
    double sortingTime_taken = ((double)sorting_timer) / CLOCKS_PER_SEC;
    double generatingTime_taken = ((double)generate_data_timer) / CLOCKS_PER_SEC;

    printf("\nAfter Merge Sort: ");
    print_array(a, n);
    printf("Generated data in: %f seconds\n", generatingTime_taken);
    printf("Sort calculation time: %f seconds\n", sortingTime_taken);
    return 0;
}