Abstract
Given two lists that are permutations of one another, the swap distance (also known as the Kendall tau distance) is the minimum number of swap operations of adjacent elements required to make the two lists the same.
Equivalently, the swap distance of two finite linear orders $\preceq$ and $\unlhd$ is the number of disagreements of the two orders, i.e. of pairs $(x,y)$ such that $x\prec y$ and $y\lhd x$.
This article defines these two notions of swap distance as well as their equivalence under the obvious isomorphism between lists and linear orders given by interpreting a list as a ranking of elements in descending order.
An efficient $O(n\log n)$ algorithm to compute the swap distance is also provided via the connection to the number of inversions of a list, for which an efficient algorithm is already available in the AFP.