Evaluation metric for an ordering algorithm There is a sentence with N words.

The words are randomly shuffled.

I have a heuristic algorithm that tries to restore the original order.

I want to evaluate my algorithm on a dataset of several hundred long sentences from the internet. 

The main goal of the algorithm is that humans looking at the restored sentence will be able to easily know what the original sentence was. So I can evaluate my algorithm by asking humans to grade the quality of the restored order. However, this is very expensive.

Another option is to count the number of words that are in their correct position in each sentence, and divide by the total number of words in all sentences. However, this is not a good measurement of the quality, because, for example, if the only mistake of my algorithm is that it put the last word first, the resulting sentence will get a score of 0, although it is quite similar to the gold standard, and a human will easily notice this.

A third option is to find the minimum number of word moves that need to be done on the algorithm output in order to achieve the gold standard. However, this seems like a non-trivial task in itself.

Can you suggest a measurement that will be both meaningful and easy to implement?
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.)