Shuffling a deck of cards is a very simple problem in randomized algorithms and something that anyone who took a course in the area should know how to do (maybe

Shuffling a deck of cards is a very simple problem in randomized algorithms and something that anyone who took a course in the area should know how to do (maybe not the fastest way, or with a full proof of correctness, but still). Here's an easy way that mirrors insertion sort: for i=0 to a.length-1 x <- random number between i and a.length-1 swap(a[i], a[x]) induction gives a proof of correctness [note: as sown points out this is known as the Knuth shuffle http://en.wikipedia.org/wiki/Knuth_shuffle http://en.wikipedia.org/wiki/Knuth_shuffle]