Sampling Gibbs measures at low temperatures is an important task but computationally challenging. Numerical evidence suggests that the infinite-swapping algorithm (isa) is a promising method. The isa can be seen as an improvement of the replica methods. We rigorously analyze the ergodic properties of the isa in the low temperature regime, deducing an Eyring-Kramers formula for the spectral gap (or Poincaré constant) and an estimate for the log-Sobolev constant. Our main results indicate that the effective energy barrier can be reduced drastically using the isa compared to the classical overdamped Langevin dynamics. As a corollary, we derive a deviation inequality showing that sampling is also improved by an exponential factor. Finally, we study simulated annealing for the isa and prove that the isa again outperforms the overdamped Langevin dynamics.