Measuring orderedness I've found this a frustrating topic to Google, and might have an entire field dedicated to it that I'm unaware of.
Given an permutation of consecutive integers, I would like a "score" (real [0:1]) that evaluates how in-order it is.
Clearly I could count the number of misplaced integers wrt the ordered array, or I could do a "merge sort" count of the number of swaps required to achieve order and normalise to the length of the array. Has this problem been considered before (I assume it has), and is there a summary of the advantages of various methods?
I also assume there is no "true" answer, but am interested in the possibilities.
 A: You might want to try including "Symmetric group" in your Google searches, if you haven't already. The set of all permutations of the first $n$ integers is a particularly example of a symmetric group.
I found this reference, which is a survey of metrics defined on symmetric groups. You can convert any of these into a norm (what you're looking for) by defining the "score" of the permutation to be its "distance" from the trivial permutation ($123\dots n$) under the metric you choose. You can then scale that to be between $0$ and $1$ by just finding the permutation that is "furthest" from the trivial one, and making that have score 1.
A: The most famous are inversion distance to the sorted list and the sum of distances that the elements have moved.  In statistics these are called Kendall's $\tau$ and Spearman's footrule.  
Search for "distance metric on symmetric group"
Search for "distance metric on S_n"
Search for "distance between rankings"
Blog entry from Peter Cameron
A: One book which treats metrics on permutations (that is, metrics on the symmetric group) is Persi Diaconis:"Group representations in probability and statistics"
which it is possible to download from here:
Link
