// Sorting is performed by generating the binary search tree and then
// constructing the sorted array on recursive walk. Neither stage makes use of
// recursive function calls. The latter one imitates it (stack, stack pointer,
// instruction pointer, return instruction pointer). A node is extremely
// compact, as the index of the node itself is the index of the corresponding
// array element, the first and the second fields are indices of nodes, that
// stand for an element, which is less, and one, which is greater,
// respectively.

int *tree_mk(void *arr_, size_t num, size_t sz, int (*cmp)(void*,void*))
{
    char (*arr)[sz] = arr_;
    int (*t)[2] = malloc(num * 2 * sizeof(int));

    t[0][0] = t[0][1] = -1;
    for (int i = 1; i < num; ++i) {
        t[i][0] = t[i][1] = -1;
        int i_ = -1, _i = 0, j;
        while (_i != -1) {
            i_ = _i;
            j = (cmp(&arr[i], &arr[i_]) < 0) ? 0 : 1;
            _i = t[i_][j];
        }
        t[i_][j] = i;
    }
    return (int *)t;
}

void tree_vec(void *dst_, void *src_, size_t sz, int (*tree)[2])
{
    char (*dst)[sz] = dst_, (*src)[sz] = src_;

    enum { IDX, RET };
    int stack[0x1000][2];
    stack[0][IDX] = stack[0][RET] = 0;

    for (int sp = 0, ip = 0; sp != -1; ++ip) {
        int idx = stack[sp][IDX],
            ret = stack[sp][RET];
        switch (ip) {
            case 0:
                if (tree[idx][0] != -1) {
                    ++sp;
                    stack[sp][IDX] = tree[idx][0];
                    stack[sp][RET] = ip;
                    ip = -1;
                }
                break;
            case 1:
                memcpy(dst++, src[idx], sz);
                break;
            case 2:
                if (tree[idx][1] != -1) {
                    ++sp;
                    stack[sp][IDX] = tree[idx][1];
                    stack[sp][RET] = ip;
                    ip = -1;
                }
                break;
            case 3:
                --sp;
                ip = ret;
                break;
        }
    }
}

void tsort(void *dst, size_t num, size_t sz, int (*cmp)(void*,void*))
{
    void *src = malloc(num * sz);
    memcpy(src, dst, num * sz);

    int *tree = tree_mk(src, num, sz, cmp);
    tree_vec(dst, src, sz, (int (*)[2])tree);

    free(tree);
    free(src);
}