Shuffle - Fisher-Yates Algorithm

The Fisher-Yates shuffle (also called Knuth shuffle) gives you a fair shuffle in $O(n)$ time.

Here's the idea: for position $i$ from $0$ to $n-1$, pick a random index $j$ where $i \leq j < n$, then swap elements at positions $i$ and $j$. This ensures each element has equal probability of ending up in any position.

Why does this work? At step $i$, you're choosing from the remaining $(n-i)$ elements with equal probability. The product of these choices gives each permutation probability $\frac{1}{n!}$.