Rather than expressing this algorithm in terms of search of a value satisfying an inequality, you can express it equivalently as a simple sum of indicators. Since you are interested in efficiency, it is also useful to vectorise the algorithm, allowing you to general $m$ independent sample values. With this setup, the algorithm can be expressed as follows:

Vectorised sampling algorithm:

1. You have a probability vector $\boldsymbol{p} = (p_1,...,p_n)$.

2. Sort this by permutation $\pi$ to get $\boldsymbol{p}_* = (p_{\pi(1)},...,p_{\pi(n)})$. (If you don't want to sort then you can just take $\boldsymbol{p}_* =\boldsymbol{p}$.)

3. Calculate the cumulative permuted probabilities $(F_1,...,F_{n-1})$ given by: $$F_k \equiv \sum_{i=1}^{k} p_{\pi(i)}.$$

4. Simulate continuous uniform random variables $U_1,...,U_m \sim \text{IID U}(0,1)$.

5. Set $K_1,...,K_m$ as follows: $$\pi(K_i) \equiv 1 + \sum_{k=1}^{n-1} \mathbb{I}( U_i > F_k ).$$ Note: In the summation formula, once you get a single zero indicator, all later indicators are zero, so you can terminate the sum early, as soon as you get a zero indicator.

From this re-statement of the sampling algorithm, we can see that the benefit of sorting the probabilities into decreasing order is that the partial sums of the reordered probabilities start with the biggest values and so they increase rapidly early on. This makes it more likely that you will get to a zero indicator earlier, which allows you to terminate the sum, thereby saving some computational time.

However my question is: does ignoring the sorting step have any other effect on the algorithm besides decreasing the performance of the algorithm?

I can't see any other difference. Mathematically the algorithm works regardless of the permutation used (including no permutation). Thus, the only difference seems to be one of computational efficiency.

... how much (when) does it actually change in terms of performance?

Presumably you get an efficiency gain from sorting when the computational cost of applying and reversing the permutation $\pi$ is smaller than the computational gain from ending the summations earlier in the last step of the algorithm. Hence, you are more likely to get a larger computational gain when the number of categories $n$ is large and/or the number of samples $m$ is large. That is, the sorting step in the algorithm will tend to be more efficient when you are generating a larger number of samples from a categorical variable with a larger number of categories.

Rather than expressing this algorithm in terms of search of a value satisfying an inequality, you can express it equivalently as a simple sum of indicators. Since you are interested in efficiency, it is also useful to vectorise the algorithm, allowing you to generate $m$ independent sample values. With this setup, the algorithm can be expressed as follows:

Vectorised sampling algorithm:

1. You have a probability vector $\boldsymbol{p} = (p_1,...,p_n)$.

2. Sort this by permutation $\pi$ to get $\boldsymbol{p}_* = (p_{\pi(1)},...,p_{\pi(n)})$. (If you don't want to sort then you can just take $\boldsymbol{p}_* =\boldsymbol{p}$.)

3. Calculate the cumulative permuted probabilities $(F_1,...,F_{n-1})$ given by: $$F_k \equiv \sum_{i=1}^{k} p_{\pi(i)}.$$

4. Simulate continuous uniform random variables $U_1,...,U_m \sim \text{IID U}(0,1)$.

5. Set $K_1,...,K_m$ as follows: $$\pi(K_i) \equiv 1 + \sum_{k=1}^{n-1} \mathbb{I}( U_i > F_k ).$$ Note: In the summation formula, once you get a single zero indicator, all later indicators are zero, so you can terminate the sum early, as soon as you get a zero indicator.

From this re-statement of the sampling algorithm, we can see that the benefit of sorting the probabilities into decreasing order is that the partial sums of the reordered probabilities start with the biggest values and so they increase rapidly early on. This makes it more likely that you will get to a zero indicator earlier, which allows you to terminate the sum, thereby saving some computational time.

However my question is: does ignoring the sorting step have any other effect on the algorithm besides decreasing the performance of the algorithm?

I can't see any other difference. Mathematically the algorithm works regardless of the permutation used (including no permutation). Thus, the only difference seems to be one of computational efficiency.

... how much (when) does it actually change in terms of performance?

Presumably you get an efficiency gain from sorting when the computational cost of applying and reversing the permutation $\pi$ is smaller than the computational gain from ending the summations earlier in the last step of the algorithm. Hence, you are more likely to get a larger computational gain when the number of categories $n$ is large and/or the number of samples $m$ is large. That is, the sorting step in the algorithm will tend to be more efficient when you are generating a larger number of samples from a categorical variable with a larger number of categories.