Improved bounds for the mixing time of the random-to-random insertion shuffle

Ben Morris, Chuan Qin

We prove an upper bound of $1.5324n\log n$ for the mixing time of the random-to-random insertion shuffle, improving on the best known upper bound of $2n\log n$. Our proof is ba…