Duplicates could also be handled by using (L+1)^n, rather than 2^n, where L is the length of the input: even if all elements are identical one will end up with a unique value p = L * (L+1)^n.

For an efficient implementation, one might want to round L+1 up to the nearest power of 2 to get crucial micro-optimisations based on instructions for bit scanning.

(I think this ends up being a very complicated phrasing of a counting sort.)

Easily solvable with a hash.

I have thought this through (I'm ashamed to admit).