Nei precedenti hint abbiamo risolto il problema, ma, come sempre, e' poi bene riconsiderarlo per le eventuali semplificazioni e per ottenere un'implementazione pratica, efficiente, conveniente.

Contare il numero di inversioni darebbe un algoritmo quadratico, che non concretizzerebbe tutti i punti messi in palio.

Parimenti, anche se limitarsi a scambi di elementi adiacenti (che porterebbe a semplificazioni utili sul piano implementativo), se da un lato sufficiente ad ordinare una permutazione (si pensi a BubbleSort), darebbe pero' un algoritmo quadratico.

Un'idea semplice che funzioni e' allora la seguente:
si scandiscono le permutazioni da sinistra verso destra ed al primo elemento fuori posto, ossia al piu' piccolo i tale che p[i] != i, si scambiano gli elementi nelle posizioni i e p[i].
Si osservi che ogni permutazione viene ordinata da al piu' n-1 di tali scambi.