Randomized vs deterministic approach for multiset equality
To understand the complexity of the randomized algorithm, you must delve into the implementation details.

Suppose $S_1,S_2$ consist of $m$ elements, each bounded by $n$ in absolute value, i.e. the input size is $O(m\log n)$. Let $P_S=\prod\limits_{w\in s}\left(x-w\right)$ be the polynomial corresponding to the set $S$. $P_{s_1},P_{S_2}$ are degree $m$ polynomials. Thus, in order to succeed with constant probability in testing whether $q(x)=P_{S_1}(x)-P_{S_2}(x)$ is the zero polynomial, you need to evaluate it at numbers in the range $[0,cm]$, for some constant $c$.

Suppose you choose $y$ uniformly at random from this range, then in order to avoid blowup in the intermediate values while computing $q(y)$, you need to compute the values modulo some $k$ (the standard trick in PIT).

Note that the blowup here is not exponential, unlike in PIT where the polynomials are given as algebraic circuits, so you can in fact directly compute $q(y)$. However, this will lead to handling $\Omega(m)$ bit numbers, which will result in quadratic running time, so you can still compute $q(y) \bmod k$ for a random $k$ chosen appropriately to save some time.

If $k$ is chosen at random from some range $[1,R]$, then a "good" event is that $k$ does not divide $q(y)$, in that case $q(y)\neq 0$ iff $q(y) \bmod k \neq 0$. To lower bound this probability, note that $k$ is prime with probability $\approx \frac{1}{\log R}$ (here you need some finite version of the prime number theorem), and that $q(y)\le (cm+n)^m$, hence it has at most $m \log (cm+n)$ different prime factors.

$
\begin{align*}
&amp;
\Pr\limits\left[\text{$k$ is prime $\land$ $k$ is not a product of $q(y)$}\right]=
\Pr\left[\text{$k$ is prime}\right]\cdot\\
&amp;
\Pr\limits\big[\text{$k$ is a product of $q(y)$} \big| \text{$k$ is prime}\big]\approx \frac{1}{\log R}\left(1-\frac{\log (cm+n)^m}{R/\log R}\right)
\end{align*}
$

Choosing $R=(m+n)^2$ suffices to make the above probability high enough, and yields constant success probability after $\approx\log R$ evaluations. Each evaluation requires $O(m)$ additions/multiplications of numbers with $\log R$ bits, thus the overall running time is $O(m\log ^2 R\log\log R)$, which is worse than sorting. Perhaps sharper bounds on the success probability will allow you to get rid of one of the logarithmic factors, but taking numeric operations into account will eventually show that you cant beat naive sorting. However, the randomized approach is not without merits, as it allows you to determine multiset equality between two parties with logarithmic communication (you only need to send $y,k$ and the evaluations of $P_{S_1},P_{S_2}$ on $y$ modulo $k$).