Sorting a row of cards

Ingredients: five cards numbered one to five, face up in a row in the order four, two, five, one, three; a table; patience.

Ingredients: $n=5$ cards in the row $(4,2,5,1,3)$.

$n=5,(4,2,5,1,3)$.

Method: start with the second card. Compare it with the card on its left. If that one is bigger, swap them, and keep swapping until the card on the left is smaller or you reach the start. Then do the same for the third card, the fourth and the fifth.

Method: for $i=2,3,4,5$, compare card $i$ with its left neighbour and swap while the left one is bigger.

$i=2,\dots ,5$: while $x_{i-1}>x_i$, swap; $s$ counts the swaps.

In this row I made six swaps in all, and the row ended as one, two, three, four, five. Six is exactly the number of pairs that were in the wrong order: four before two, four before one, four before three, two before one, five before one and five before three.

Here: $6$ swaps, and the row becomes $(1,2,3,4,5)$. The pairs in the wrong order are $(4,2),(4,1),(4,3),(2,1),(5,1),(5,3)$, that is $6$ of them, one swap for each.

$I=\{(i,j)\mid i<j,x_i>x_j\}$, $s=|I|=6$, $(1,2,3,4,5)$.

Serving suggestion: a row in exactly the opposite order needs the most swaps. Every pair is wrong, which is five times four over two, ten swaps. Ten cards in reverse need forty-five. Twice the cards, more than four times the work.

Worst case: a reversed row, all $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ pairs wrong, so $10$ swaps. For $n=10$ it is $\left(\genfrac{}{}{0ex}{}{10}{2}\right)=45$. Doubling $n$ multiplies the work by more than $4$.

Worst: $|I|=\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$; $n=10\Rightarrow \left(\genfrac{}{}{0ex}{}{10}{2}\right)=45$; $\left(\genfrac{}{}{0ex}{}{2n}{2}\right)>4\left(\genfrac{}{}{0ex}{}{n}{2}\right)$.