occhio che c'è un errore che mi sono portato dietro dal copia incolla del tuo codice, il secondo ciclo di ordinamento è strlen(p2) e non di p1, fnziona in tutti quei casi in cui p2 è maggiore o uguale a p1 è per questo che non te ne sei accorto.

anzi per fare ancora meglio andando sulla scia del consiglio di who direi che all'inizio ci fai subito un bel controllo su le due strlen ed eviti di fare gli ordinamenti e i confronti gia se le due lunghezze sono diverse.