Definitions:
Let an be the maximum number of moves required to turn a permutation of 1,2,…,n into increasing order.
Let X (given any arrangement) be the number of pairs in decreasing (i.e., the wrong) order.
We note that 0≤X≤nC2, that the cards are in increasing order iff X=0 (and decreasing order iff X=nC2), and that given any arrangement not in either of thee two states it is possible to increase or decrease X by 1, by changing around two adjacent cards.
Lemma 1: a4=3
Here if X≤3, then we can reduce it to 0 by a sequence of changing around adjacent cards. If X≥4, we can increase it to 6 in 2 moves, then swap the cards around.
Lemma 2: a5=4
If X≤4, then we can reduce it to 0 by changing one pair of cards at a time.
If X≥7, then we can increase it to 10 similarly and then swap all the cards around
If X=5 and there are three cards in either decreasing or increasing order, then we can swap their order around, at which point X≤3 or X≥8. From here we can finish as before, in only three moves.
So we may assume that there are no consecutive three cards in increasing or decreasing order. Therefore the row of cards goes 'up-down-up-down' or 'down-up-down-up'. We can say that it goes 'down-up down-up' without loss of generality because an 'up-down-up-down' order is equivalent to one 'down-up-down-up' with the card 1 interchanged with 5 and 2 with 4.
Let us call the first card a, the second b, and c,d,e for the third, fourth and fifth cards.
Clearly either b=1 or d=1, since a,c>b and c,e>d. If b=1, then we begin by swapping a and b around, from which point we only have four cards to arrange, which takes 3 moves by Lemma 1.
So we assume that d=1.
Since a,c>b, b=2 or 3.
If b=3 then e=5 and we have two cases to consider: 43512 and 53412. We can check that these are possible in 4 moves.
If b=2, thene= one of 3,4,5. If e=5 then we are done by Lemma 1. If e=4 or 3, then there are 4 cases to consider: 3251452314 42513 52413. We can easily check that these are possible in 4 moves.
Hence any arrangement of 1,2,3,4,5 can be made increasing in 4 moves, that is a5=4
Lemma 3: an≤an−1+2
Suppose we have a permutation of 1,2…n, and that the last card is k. We arrange the other n−1 cards into increasing order: this takes an−1 moves at most. We then have 1,2,…(k−1),(k+1)…n,k. We can swap (k+1),…n around, at which point the arrangement is 1,2,…(k−1),n,(n−1)…k. Then we swap the bit from n to k around.
Thus we have arranged n cards into increasing order in an−1+2 moves, proving this Lemma.
We have that a5=4, by Lemma 3 a6≤6, a7≤8, a8≤10, a9≤12. Therefore it takes at most 12 moves to arrange cards 1 to 9 in increasing order.