Problem
COM-B2-M05-P011 Sorting by Adjacent Swaps
The numbers \(1,2,\ldots,n\) are arranged in an arbitrary order. If two neighbouring numbers are in the wrong order, they may be swapped. Prove that the process cannot continue forever.
Use the number of inversions.
An inversion is a pair of numbers in which the larger one stands to the left of the smaller one. The number of inversions is a nonnegative integer.
Swapping a neighbouring wrong pair decreases the number of inversions by exactly \(1\): that pair stops being an inversion, and the relations of these two numbers with all other numbers do not change the total number of inversions.
Therefore the number of inversions strictly decreases and cannot decrease forever. The process terminates.
This repeats the method, but here the emphasis is specifically on the monovariant.