Can I construct a PRP by sorting results of a PRF? I am using HMAC-SHA256 as a pseudorandom function family (PRF). I read somewhere that a pseudorandom permutation family (PRP) can be implemented by applying a PRF and sorting the output. 

For example, if $x_1$ mapped to $4$ under a specific key in the PRF, and $x_2$ mapped to $2$, then the PRP for $\{x_1, x_2\}$ would be $\{x_2, x_1\}$ under that same key. 

Does that make sense? Is this PRP construction secure, or do I have to implement a Luby-Rackoff construction using the PRF?
Even if this worked in principle, I don't see how this could possibly be practical to implement for any but the smallest sets, since it requires you to enumerate (and sort) the set you want to permute.

Also, it seems to me that, unless the codomain of the PRF is much larger than its domain, you're going to have an issue with ties, i.e. with inputs $x_1 \ne x_2$ for which ${\rm PRF}(x_1) = {\rm PRF}(x_2)$.  I don't see any obvious way to break such ties that could not be potentially used to distinguish the resulting PRP from a random permutation.

All that said, if you really just want to pseudorandomly shuffle a small set of values, feeding each of them to a PRF with a sufficiently large domain (like HMAC-SHA256) and sorting the values by the result should be a perfectly good and secure solution.  Specifically, consider an adversary that tries to distinguish your pseudorandom shuffle from a truly random shuffle.  For such an adversary to succeed (with probability greater than &frac12;), they must either:


somehow distinguish the PRF from a random function, or
observe a collision among the PRF outputs.


The probability of option 1 will depend on the PRF (and on the assumed capabilities of the attacker), but it must be negligibly small for all practical attackers for the PRF to be deemed secure.  On the other hand, assuming that the PRF is not distinguishable from a random function, the second probability can be calculated:

Specifically, given $k$ inputs to a PRF with an $n$-element codomain (where e.g. $n = 2^{256}$ for HMAC-SHA256), the probability $p$ of observing at least one collision is less than the expected number of collisions, which itself equals $\frac{k^2 - k}{2n} &lt; \frac{k^2}{2n}$.  Thus, for example, if $k \le 2^{64}$ and $n = 2^{256}$, then $p &lt; \frac{(2^{64})^2}{2\cdot2^{256}} = 2^{-129}$.