#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>

typedef struct {
    int* res;
    const int* arr1;
    int n;
    const int* arr2;
    int m;
} pack_t;

int* create_arr(int n);
void print_arr(const char* name, const int* arr, int n);
void merge_arr(int* res, const int* arr1, int n, const int* arr2, int m);
void delete_arr(int* arr);
void* merge_impl(void* data);
int comp(const void* l, const void* r);

const int SIZE_ARR1 = 10;
const int SIZE_ARR2 = 15;
const int MAX_VAL = 100;

int main() {
    srand(time(NULL));
    int* arr1 = create_arr(SIZE_ARR1);
    int* arr2 = create_arr(SIZE_ARR2);
    int* res = create_arr(SIZE_ARR1 + SIZE_ARR2);
    qsort(arr1, SIZE_ARR1, sizeof(int), comp);
    qsort(arr2, SIZE_ARR2, sizeof(int), comp);
    print_arr("arr1", arr1, SIZE_ARR1);
    print_arr("arr2", arr2, SIZE_ARR2);
    merge_arr(res, arr1, SIZE_ARR1, arr2, SIZE_ARR2);
    print_arr("res", res, SIZE_ARR1 + SIZE_ARR2);
    delete_arr(arr1);
    delete_arr(arr2);
    delete_arr(res);
    return 0;
}

int* create_arr(int n) {
    int* res = (int*) malloc(n * sizeof(int));
    int full = 2 * MAX_VAL + 1;
    for (int i = 0; i < n; ++i) {
        res[i] = rand() % full - MAX_VAL;
    }
    return res;
}

void print_arr(const char* name, const int* arr, int n) {
    printf("%s:\n", name);
    for (int i = 0; i < n; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
}

void merge_arr(int* res, const int* arr1, int n, const int* arr2, int m) {
    int h1 = n / 2, h2 = m / 2;
    pack_t data1 = { res, arr1, h1, arr2, h2 };
    pack_t data2 = { res + h1 + h2, arr1 + h1, n - h1, arr2 + h2, m - h2 };
    pthread_t thread1, thread2;
    pthread_create(&thread1, NULL, merge_impl, &data1);
    pthread_create(&thread2, NULL, merge_impl, &data2);
    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);
}

void delete_arr(int* arr) {
    free(arr);
}

void* merge_impl(void* data) {
    pack_t* d = (pack_t*) data;
    int i = 0, j = 0;
    int len = d->n + d->m;
    for (int k = 0; k < len; ++k) {
        if (i < d->n && j < d->m) {
            d->res[k] = d->arr1[i] < d->arr2[j] ? d->arr1[i++] : d->arr2[j++];
        } else {
            d->res[k] = i < d->n ? d->arr1[i++] : d->arr2[j++];
        }
    }
    pthread_exit(NULL);
}

int comp(const void* l, const void* r) {
    return *(int*)l - *(int*)r;
}