Evaluation metric for an ordering algorithm
One standard measure is the Kendall tau distance, which is the number of "inversions", i.e. positions $i &lt; j$ such that $\pi(i) &gt; \pi(j)$. It is also the number of transpositions $(k \; k+1)$ you need to apply to sort $\pi$, or vice versa, the number of such transpositions needed to generate $\pi$. (So it's the distance metric in the Cayley graph of $S_n$ with respect to the transpositions $(k \; k+1)$, which form a generating set.)