# How Python random shuffle works?

How shuffle from random works in Python?

I ask because it works very fast. When I try to write shuffle it works 1 minute for 10^6 element, but Python shuffle does that in 8 sec?

• Why not just look at the source code? Oct 28, 2013 at 8:34
• best shuffle algorithm is the fisher-yates shuffle, it runs in O(n) time and is proven to be a perfect shuffle (assuming good random source) Oct 28, 2013 at 8:39
• @ratchetfreak: Python uses Fisher-Yates. Oct 28, 2013 at 10:03
• What is your algorithm for shuffle? Oct 28, 2013 at 14:48
• @sloth, by the way, Raymond Hettinger proposed a universal practice of docs linking back to source code back in 2011. Jul 26, 2015 at 20:22

Python's `random.shuffle` uses the Fisher-Yates shuffle, which runs in O(n) time and is proven to be a perfect shuffle (assuming a good random number generator).

It iterates the array from the last to the first entry, switching each entry with an entry at a random index below it.

The basic process of Fisher–Yates shuffling is similar to randomly picking numbered tickets out of a hat, or cards from a deck, one after another until there are no more left. What the specific algorithm provides is a way of doing this numerically in an efficient and rigorous manner that, properly done, guarantees an unbiased result...

The modern... solution is to move the "struck" numbers to the end of the list by swapping them with the last unstruck number at each iteration. This reduces the algorithm's time complexity to O(n), compared to O(n2) for the naive implementation. This change gives the following algorithm (for a zero-based array).

``````To shuffle an array a of n elements (indices 0..n-1):
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
``````