Usei bubble sort para ordenar, veja se é assim.
Só fiz um teste com os valores de 1 a 10.
#include <stdio.h>int mdc(int, int);int inverte(int);void troca(int *, int *);void ordena(int *, int, int);int main(){ int i, m, n; scanf("%d %d%*c", &n, &m); int vetor[n]; for(i = 0; i < n; i++){ scanf("%d%*c", &vetor[i]); } ordena(vetor, m, n); printf("\n\n"); for(i = 0; i < n; i++){ printf(" %d", vetor[i]); } printf("\n"); return 0;}void ordena(int *v, int m, int n){ int i, continua = 1; while(continua){ continua = 0; for(i = 0; i < n - 1; i++){ if(mdc(v[i], m) == mdc(v[i + 1], m)){ if(inverte(v[i]) > inverte(v[i + 1])){ troca(&v[i], &v[i + 1]); continua = 1; }else if(inverte(v[i] == v[i + 1])){ if(v[i] > v[i + 1]){ troca(&v[i], &v[i + 1]); continua = 1; } } }else if(mdc(v[i], m) < mdc(v[i + 1], m)){ troca(&v[i], &v[i + 1]); continua = 1; } } }}void troca(int *a, int *{ int aux = *a; *a = *b; *b = aux;}int inverte(int a){ int x = 0; while(a){ if(x) x *= 10; x += a % 10; a /= 10; } return x;}int mdc(int a, int { int aux; while({ aux = b; b = a % b; a = aux; } return a;}