You are given an array of n distinct integers. A swap is interchanging the value of two positions in the array. What is the minimum number of swaps required to sort the array?

For example: If the array is [2,1,3], we need only 1 swap (swap 1 and 2). If the array is [2,3,1], we need 2 swaps (swap 2 and 3, then swap 1 and 3).

- via Stack Overflow

Interpret your array as a permutation, and write it in cycle notation. Then the number of swaps needed is the sum of the lengths of all cycles except the one-cycles.

Oops, slight mistake. What you want is

sum_{all cycles} (length of cycle - 1)

This is one way to sort the array, but how do we know this is the minimum number of swaps needed?

@Lizard: Proof: After each swap, the number of permutation cycles can increase by at most 1.