Found you from

**ephermata**. I'm pretty sure pure shuffling has to be at least O(n log n), since the naïve version allocates a full binary tree over the set to be shuffled. Even if you deforest and don't allocate that, there are n log n choice points, n log n examinations of a random value.

You might enjoy Oleg Kiselyov's perfect shuffle in Haskell, available at

http://okmij.org/ftp/Haskell/perfect-shuffle.txt