#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static size_t ipow(size_t a, unsigned b) { 
    size_t r = 1; while (b--) r *= a; return r;
}

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


static void reorder_blocks(int *base, size_t block_sz, size_t M,const size_t *idx)
{
    size_t group_sz = block_sz * M;
    int *tmp = malloc(group_sz * sizeof(int));
    for (size_t j = 0; j < M; ++j)
        memcpy(tmp + j*block_sz, base + idx[j]*block_sz, block_sz*sizeof(int));
    memcpy(base, tmp, group_sz * sizeof(int));
    free(tmp);
}


void sort_ND(int *a, unsigned N, size_t M)
{
    const size_t total = ipow(M, N);


    for (size_t off = 0; off < total; off += M)
        qsort(a + off, M, sizeof(int), cmp_int);

    for (unsigned level = 2; level <= N; ++level) {
        size_t block_sz = ipow(M, level - 1);
        size_t group_sz = block_sz * M;
        size_t groups   = total / group_sz;

        long *sums = malloc(M * sizeof(long));
        size_t *idx = malloc(M * sizeof(size_t));

        for (size_t g = 0; g < groups; ++g) {
            int *base = a + g * group_sz;


            for (size_t j = 0; j < M; ++j) {
                long s = 0;
                int *p = base + j * block_sz;
                for (size_t t = 0; t < block_sz; ++t) s += p[t];
                sums[j] = s;
                idx[j] = j;
            }

            for (size_t i = 0; i + 1 < M; ++i)
                for (size_t j = i + 1; j < M; ++j)
                    if (sums[idx[j]] < sums[idx[i]]) {
                        size_t tmp = idx[i]; idx[i] = idx[j]; idx[j] = tmp;
                    }


            reorder_blocks(base, block_sz, M, idx);
        }
        free(sums); free(idx);
    }
}


int main(void) {
    size_t M = 3; unsigned N = 2;
    int a[] = { 0,3,2,  9,4,5,  4,1,3 };
    sort_ND(a, N, M);

    for (size_t i = 0; i < M; ++i) {
        for (size_t j = 0; j < M; ++j) printf("%d ", a[i*M + j]);
        printf("\n");
    }
    return 0;
}