[Haskell-cafe] Linear shuffle

[Scott Turner]

The shuffling algorithms mentioned so far are comparable to 
insertion/selection sort. I had come up with a shuffler that relates to 
quicksort, in that it partitions the input randomly into lists and works 
recursively from there. It looks efficient and works out well in Haskell.

shuffle [] = return []
shuffle [c] = return [c]
shuffle deck0 = partition deck0 [] []
    where
        partition [] p0 p1 = do
                s1 <- shuffle p0
                s2 <- shuffle p1
  return (s1 ++ s2)
        partition (d : deck) p0 p1 = do
  n <- randomRIO (0::Int,1)
  case n of
   0 -> partition deck (d : p0) p1
   1 -> partition deck p0 (d : p1)

Analogous to quicksort's bad behavior in the worst case, an invocation of 
'partition' is not guaranteed to make any progress with the shuffling, 
because one of the output lists might receive all of the input items.