#include <assert.h>  // assert
#include <stddef.h>  // size_t
#include <stdlib.h>  // qsort, malloc, realloc, free, exit
#include <stdio.h>   // printf, scanf
#include <string.h>  // memcpy

struct vec{
    void *data;
    size_t size;
    size_t capacity;
    size_t elem_size;
};

int vec_init(struct vec *v, size_t elem_size){
    v->elem_size = elem_size;
    v->size = 0;
    v->capacity = 4;
    v->data = malloc(v->capacity * elem_size);
    if(v->data == NULL){
        v->capacity = 0;
        return 0;
    }
    return 1;
}

void vec_free(struct vec *v){
    free(v->data);
    v->data = NULL;
    v->size = 0;
    v->capacity = 0;
}

void *vec_get(struct vec *v, size_t i){
    assert(i < v->size);
    return (char *)v->data + i * v->elem_size;
}

int vec_push(struct vec *v, void *elem){
    if(v->size >= v->capacity){
        size_t new_capacity = v->capacity * 2;
        void *new_data = realloc(v->data, new_capacity * v->elem_size);
        if(new_data == NULL){
            return 0;
        }
        v->data = new_data;
        v->capacity = new_capacity;
    }
    memcpy((char *)v->data + v->size * v->elem_size, elem, v->elem_size);
    v->size++;
    return 1;
}

void dvq(void *ptr, size_t l, size_t r, size_t elem_size, int (*cmp)(const void *, const void *), struct vec *pom){
    if(l >= r) return;

    size_t mid = (l + r) / 2;
    dvq(ptr, l, mid, elem_size, cmp, pom); dvq(ptr, mid + 1, r, elem_size, cmp, pom);

    size_t i = l, j = mid + 1, akt = l;
    while(i <= mid && j <= r){
        void *ei = (char *)ptr + i * elem_size;
        void *ej = (char *)ptr + j * elem_size;
        if(cmp(ei, ej) <= 0){
            memcpy((char *)pom->data + akt * elem_size, ei, elem_size);
            akt++; i++;
        }else{
            memcpy((char *)pom->data + akt * elem_size, ej, elem_size);
            akt++; j++;
        }
    }
    while(i <= mid){
        memcpy((char *)pom->data + akt * elem_size, (char *)ptr + i * elem_size, elem_size);
        akt++; i++;
    }
    while(j <= r){
        memcpy((char *)pom->data + akt * elem_size, (char *)ptr + j * elem_size, elem_size);
        akt++; j++;
    }

    for(size_t k = l; k <= r; k++) memcpy((char *)ptr + k * elem_size, (char *)pom->data + k * elem_size, elem_size);
}

void msort(void *ptr, size_t ile, size_t size, int (*cmp)(const void *, const void *)){
    if(ile <= 1) return;

    struct vec pom;
    if(!vec_init(&pom, size)) exit(1);

    while(pom.capacity < ile){
        size_t new_cap = pom.capacity * 2;
        void *new_data = realloc(pom.data, new_cap * size);
        if(new_data == NULL){
            vec_free(&pom);
            exit(1);
        }
        pom.data = new_data;
        pom.capacity = new_cap;
    }
    pom.size = ile;

    dvq(ptr, 0, ile - 1, size, cmp, &pom);

    vec_free(&pom);
}

struct pair{
    int first;
    int second;
};

int cmp_int(const void *a, const void *b){
    int ia = *(const int *)a;
    int ib = *(const int *)b;
    if(ia < ib) return -1;
    if(ia > ib) return 1;
    
    
    return 0;
}





int cmp_char(const void *a, const void *b){
    char ca = *(const char *)a;
    char cb = *(const char *)b;
    
    if(ca < cb) return -1;
    if(ca > cb) return 1;
    return 0;
}



int cmp_pair(const void *a, const void *b){
    const struct pair *pa = a;
    const struct pair *pb = b;
    
    if(pa->first < pb->first) return -1;
    if(pa->first > pb->first) return 1;
    return 0;
}




int main(void){
    int inty[] = {5, 2, 9, 1, 5, 6};
    size_t inty_ile = sizeof(inty) / sizeof(inty[0]);
    msort(inty, inty_ile, sizeof(int), cmp_int);
    printf("inty: ");
    for(size_t i = 0; i < inty_ile; i++) printf("%d ", inty[i]);
    printf("\n");


    char chary[] = {'z', 'a', 'k', 'b', 'm'};
    size_t chary_ile = sizeof(chary) / sizeof(chary[0]);
    msort(chary, chary_ile, sizeof(char), cmp_char);
    printf("chary: ");
    for(size_t i = 0; i < chary_ile; i++) printf("%c ", chary[i]);
    printf("\n");



    struct pair pary[] = {{2, 1}, {1, 2}, {2, 2}, {1, 1}};
    size_t pary_ile = sizeof(pary) / sizeof(pary[0]);
    msort(pary, pary_ile, sizeof(struct pair), cmp_pair);
    printf("pary (stabilne): ");
    for(int i = 0; i < 4; i++) printf("(%d,%d), ", pary[i].first, pary[i].second);
    printf("\n");

    return 0;
}