The basic idea behind our solution is the following.

Compute first the number of appearances ~Na[x]~ for elements ~x = 1, 2, 3~ in the input sequence. Then the sorted sequence consists of ~Na[1]~ number of ~1~'s followed by ~Na[2]~ number of ~2~'s and then ~Na[3]~ number of ~3~'s.

We say that an element ~x~ is in the place of ~y~'s if the current position of ~x~ equals the position of an element ~y~ in the sorted sequence. We use the abbreviation ~x:y~ to denote an element ~x~ in place of ~y~'s.

Next, compute ~NEP[x,y]~, the number of elements ~x~'s in the place of ~y~'s for all ~x~ and ~y~. Consider the following algorithm written in pseudocode.

NoCh:=0;
While Not Sorted(S) Do Begin
  If there are x and y in each other's place Then Begin
    Inc(NoCh);
    Exchange x and y;
    Update NEP[x,y] and NEP[y,x];
  End Else Begin
    If (NEP[1,2]>0) And (NEP[3,1]>0) Then Begin
      Exchange a pair of elements 3:1 and 1:2 ;
      Update NEP[1,2] And NEP[3,1];
      Inc(NoCh);
    End;
    If (NEP[2,1]>0) And (NEP[1,3]>0) Then Begin
      Exchange a pair of elements 2:1 and 1:3 ;
      Update NEP[2,1] And NEP[1,3];
      Inc(NoCh);
    End;
  End;
End;

First, we show that the number of exchange operations performed by the algorithm can be given by the expression:

$$\displaystyle Ch(S) = \min(NEP[1,2], NEP[2,1]) + \min(NEP[1,3], NEP[3,1]) + \min(NEP[2,3], NEP[3,2]) + 2 \times |NEP[1,2]-NEP[2,1]|$$

After performing ~\min(NEP[x,y], NEP[y,x])~ exchange operations for all ~x \ne y~, the resulting sequence contains ~NEP[1,2]-NEP[2,1]~ number of elements ~1:2~, ~2:3~, ~3:1~ if ~NEP[1,2] > NEP[2,1]~ and ~1:3~, ~2:1~, ~3:2~ if ~NEP[1,2] < NEP[2,1]~. In the first case, the algorithm makes exchange ~2:1~ and ~1:3~, which results in an element ~2~ in place of ~3~. Therefore in the next iteration, an exchange of ~2:3~ and ~3:2~ will be performed. The second case is similar. We conclude that the expression ~Ch(S)~ is correct for the number of exchange operations performed by the algorithm.

Let us denote by ~OCh(S)~ the minimal number of exchange operations needed to make the sequence ~S~ sorted. We shall prove that ~Ch(S) = OCh(S)~. The proof is by induction on the value ~OCh(S)~.

If ~OCh(S) \in \{0, 1\}~ then the statement obviously holds.

Assume that ~Och(S) = Ch(S)~ for all ~S~ if ~OCh(S) < k~, for some ~k > 1~. Let ~S~ be a sequence and ~OCh(S) = k~.

Consider an optimal sequence of exchange operations that makes ~S~ sorted. Assume that the first exchange operation exchanges elements ~x_1:y_1~ and ~x_2:y_2~ (or ~x_1:y_2~ and ~x_1:y_1~) and denote by ~S'~ the resulting sequence. We distinguish the following two cases:

C1: x1=y2 and x2=y1 or
    NEP[1,2]>NEP[2,1] and x1=1, y1=2, x2=3, y2=1 or
                          x1=1, y1=2, x2=2, y2=3 or
                          x1=3, y1=1, x2=2, y2=3 or
    NEP[1,2]>NEP[2,1] and x1=2, y1=1, x2=3, y2=2 or
                          x1=2, y1=1, x2=1, y2=3 or
                          x1=3, y1=2, x2=1, y2=3 or
C2: all other combinations for x1, y1, x2, y2.

We can verify by a routine calculation that ~Ch(S') = Ch(S)-1~ in case C1 and ~Ch(S') \ge Ch(S)~ in case C2. In case C1, we obtain by the inductive hypotheses that the algorithm performs ~Ch(S) = Ch(S')+1 = OCh(S')+1 = OCh(S)~ exchange operations.

Case C2 contradicts the optimality condition, therefore an optimal sequence of exchange operations can only start with an exchange specified in case C1.

In order to develop an efficient algorithm that constructs a sequence of exchange operations, we introduce the array ~First~, that ~First[x,y]~ always contains the first position of ~x~ in place of ~y~'s. ~First[x,y]~ is computed by the preprocess procedure and is updated after each exchange operation.