#include <stddef.h>
#include <malloc.h>
#include <string.h>

int comparator(const void *left, const void *right) {
    //assert(left != NULL);
    //assert(right != NULL);
    return *((const int *) left) - *((const int *) right);
}


void mergesort(void *array, size_t elements, size_t element_size ,int (*comparator)(const void *, const void *)) {
    size_t mid;
    size_t l = 0;
    size_t r = elements;
    if (l == r - 1) {
        return;
    }
    mid = ((l + r) / 2);
    size_t first = l;
    size_t second = mid;
    mergesort(array, mid - l, element_size, comparator);
    mergesort(array + mid * element_size, r - mid, element_size, comparator);
    void *dop = (void *) malloc((elements + 5) * element_size);

    for (int i = 0; i < elements; i++) {
        if (second < r && comparator(array + first * element_size, array + second * element_size) <= 0 && first < mid) {
            memcpy(dop + i * element_size, array + first * element_size, element_size);
            first ++;
        } else {
            if (second < r) {
                memcpy(dop + i * element_size, array + second * element_size, element_size);
                second ++;
            } else {
                memcpy(dop + i * element_size, array + first * element_size, element_size);
                first ++;
            }
        }
    }

    for (int i = 0; i < elements; i++) {
        memcpy(array + l * element_size + i * element_size, dop + i * element_size, element_size);
    }
    free(dop);
}