Quantum algorithm can give answers with 100% certainty. For example, Grover's algorithm can give the answer with certainty when the ratio of "good" items to "bad" items satisfies some constraints. The uncertainty exists when the output state is not an eigenstate of the measurement observable.
On the other hand, Shor's algorithm is a hybrid of classical and quantum steps. The quantum order finding step might fail to find an appropriate "order" in an iteration, but you cannot say it is incorrect. Instead, the measurement gives one of the phases of the unitary operator $U|y\rangle =|xy \text{(mod } N\text{)}\rangle$, the phase can then be used to derive the order classically. However only some of these orders can be used to find the factors. If the order found after measurement is not appropriate, Shor's algorithm need to repeat the quantum step (together with some classic steps). (There are multiple phases because the input $|1\rangle$ is a superposition of many eigenvectors associated with these phases.)
Many word theory is more philosophical than computationally or informational. Using this theory, at least one of the world will find an appropriate order in the first iteration and Shor's algorithm will stop quicker. In some world, all iterations fail (as long as you continue) to find the appropriate order and Shor's algorithm will not finish. Of course, Shor proved that the probability of not finishing can be arbitrarily low given enough iterations.
Some people reject many world theory using a joke: you can believe it in the other worlds. To me, the challenge is where does the (exponential, enormous) extra energy come as worlds split all the time?
