Line 3 chooses a random number between 1 and n3. We use a range of 1 to n3 to make it likely that all the priorities in P are unique. Let us assume that all the priorities are unique.
The time-consuming step in this procedure is the sorting in line 4. After sorting, if P[i] is the jth smallest priority, then A[i] will be in position j of the output. In this manner we obtain a permutation. It remains to prove that the procedure produces a uniform random permutation, that is, that every permutation of the numbers 1 through n is equally likely to be produced.
Lemma 5.4: Procedure PERMUTE-BY-SORTING produces a uniform random permutation of the input, assuming that all priorities are distinct
Proof: We start by considering the particular permutation in which each element A[i] receives the ith smallest priority. We shall show that this permutation occurs with probability exactly 1/n!. For i = 1, 2, ..., n, let Xi be the event that element A[i] receives the ith smallest priority. Then we wish to compute the probability that for all i, event Xi occurs, which is
Pr {X1 ∩ X2 ∩ X3 ∩ ··· ∩ Xn-1 ∩ Xn}.
this probability is equal to: Pr {X1} · Pr{X2 | X1} · Pr{X3 | X2 ∩ X1} · Pr{X4 | X3 ∩ X2 ∩ X1}
Pr{Xi | Xi-1 ∩ Xi-2 ∩ ··· ∩ X1} Pr{Xn | Xn-1 ∩ ··· ∩ X1}.
We have that Pr {X1} = 1/n because it is the probability that one priority chosen randomly out of a set of n is the smallest. Next, we observe that Pr {X2 | X1} = 1/(n - 1) because given that element A[1] has the smallest priority, each of the remaining n - 1 elements has an equal chance of having the second smallest priority. In general, for i = 2, 3, ..., n, we have that Pr {Xi | Xi-1 ∩ Xi-2 ∩ ··· ∩ X1} = 1/(n - i 1), since, given that elements A[1] through A[i - 1] have the i - 1 smallest priorities (in order), each of the remaining n - (i - 1) elements has an equal chance of having the ith smallest priority. Thus, we have
and we have shown that the probability of obtaining the identity permutation is 1/n!.
We can extend this proof to work for any permutation of priorities. Consider any fixed permutation σ = < σ(1), σ(2), ..., σ(n) > of the set {1, 2, ..., n}. Let us denote by ri the rank of the priority assigned to element A[i], where the element with the jth smallest priority has rank j. If we define Xi as the event in which element A[i] receives the σ(i)th smallest priority, or ri = σ(i), the same proof still applies. Therefore, if we calculate the probability of obtaining any particular permutation, the calculation is identical to the one above, so that the probability of obtaining this permutation is also 1/n!.
Lemma 5.5: Procedure RANDOMIZE-IN-PLACE computes a uniform random permutation.
Proof: We use the following loop invariant:
We need to show that this invariant is true prior to the first loop iteration, that each iteration of the loop maintains the invariant, and that the invariant provides a useful property to show correctness when the loop terminates.
Let us examine the ith iteration. Consider a particular i-permutation, and denote the elements in it by <x1, x2, ..., xi>. This permutation consists of an (i - 1)-permutation <x1, ..., xi-1> followed by the value xi that the algorithm places in A[i]. Let E1 denote the event in which the first i - 1 iterations have created the particular (i - 1)-permutation <x1,..., xi-1> in A[1 .. i - 1]. By the loop invariant, Pr {E1} = (n - i 1)!/n!. Let E2 be the event that ith iteration puts xi in position A[i]. The i-permutation <x1, ..., xi> is formed in A[1 .. i] precisely when both E1 and E2 occur, and so we wish to compute Pr {E2 ∩ E1}. we have
Pr {E2 ∩ E1} = Pr{E2 | E1}Pr{E1}.
The probability Pr {E2 | E1} equals 1/(n-i 1) because in line 3 the algorithm chooses xi randomly from the n - i 1 values in positions A[i .. n]. Thus, we have
Thus, RANDOMIZE-IN-PLACE produces a uniform random permutation.