More natural/preferred way to shuffle an array

Learning
6

Here is a somehow more functional way of shuffling a list. It is not as efficient in practice as Knuth shuffle algorithm, the expected time complexity is only O(n log n). But it also makes clear that it uses O(n log n) random bits (expected again), and that is the information-theory lower bound. I like the fact that it mirrors the quicksort algorithm.

let rec shuffle = function
  | [] -> []
  | [single] -> [single]
  | list -> 
    let (before, after) = List.partition (fun elt -> Random.bool ()) list in 
    List.rev_append (shuffle before) (shuffle after)
5 Likes