#include <stdbool.h>
#include <string.h>
 
int cmp(const void *i, const void *j)
{
    return (*(const int *)i) - (*(const int *)j);
}
 
void swap(void *pe, void *pr, int elem_size)
{
    char tmp;
    char *p1 = pe;
    char *p2 = pr;
    for (int i = 0; i < elem_size; i++)
    {
        tmp = *p1;
        *p1 = *p2;
        *p2 = tmp;
        p1++;
        p2++;
    }
}
 
bool is_sorted(void *base, int n, int elem_size, int (*cmp)(const void *, const void *))
{
    char *pb = base;
    char *pe = pb + n * elem_size;
    for (char *cur1 = pb; cur1 < pe - elem_size; cur1 += elem_size)
        if (cmp(cur1, cur1 + elem_size) > 0)
            return true;
    return false;
}
 
void mysort(void *base, int n, int elem_size, int (*cmp)(const void *, const void *))
{
    if (n == 0)
        return;
 
    char *pb = base;
    char *pe = pb + n * elem_size;
 
    int in = 1;                                // первый нечетный индекс
    int tin = in;                              // сохраняем его
    int cn = (n - 1) % 2 == 0 ? n - 1 : n - 2; //взятие последнего четного индекса элемента
    int tcn = cn;                              // сохранение
    char *tmpn, *tmpc;
 
    while (is_sorted(base, n, elem_size, cmp))
    {
        tmpn = pb + in * elem_size; // фиксируем нечетный эл
 
        for (char *cur1 = tmpn; cur1 < pe; cur1 += elem_size)
        {
            if (cmp(tmpn, cur1) > 0)
                swap(tmpn, cur1, elem_size);
        }
 
        tmpc = pb + cn * elem_size; // фиксируем четный элемент последний
        for (char *cur1 = tmpc; cur1 < pe; cur1 += elem_size)
            if (cmp(tmpc, cur1) > 0)
                swap(tmpc, cur1, elem_size);
 
        if (cn - 2 < 0)
            cn = tcn;
        else
            cn -= 2;
 
        if (in + 2 > n)
            in = tin;
        else
            in += 2;
    }
}