Explain how to implement the algorithm PERMUTE-BY-SORTING to handle the case in which two or more priorities are identical. That is, your algorithm should produce a uniform random permutation, even if two or more priorities are identical.

The simplest approach would be to verify if \(P\) is unique before using it to sort \(A\). Exercise 5.3-5 tells us the probability of \(P\) containing all unique elements is at least \(1 - \frac{1}{n}\) so it is likely that we will not need to generate \(P\) more than twice.

Alternatively, we could bundle together duplicate sort keys and call PERMUTE-BY-SORTING again on the subset of values that contain duplicate keys. These values will reside sequentially in the output and this secondary call to PERMUTE-BY-SORTING would simply determine the order of their sequence. This approach is similar to the one previously discussed in that a collision results in generating another \(P\) array, but with the near-guarantee that the value of \(n\) will be smaller (all cases except where there are \(n\) collisions).

Which of these approaches to implement depends heavily on how line 5 of PERMUTE-BY-SORTING is implemented. Since the pseudocode in the text doesn’t belabor itself with describing how this is implemented, I opted to do the same.