What is the most elegant way of bubble-sorting in F#?

F# is an impure language. Don't be puritanical about purity. Here is a simpler and more elegant impure bubblesort in F#:

let rec sort (a: int []) =
  let mutable fin = true
  for i in 0..a.Length-2 do
    if a.[i] > a.[i+1] then
      let t = a.[i]
      a.[i] <- a.[i+1]
      a.[i+1] <- t
      fin <- false
  if not fin then sort a

using bubble sort in a functional language isn't very efficient, because the implementation has to reverse the list many times (and this can't be really implemented very efficiently for immutable lists).

Anyway, the example from Erlang can be rewritten to F# like this:

let sort l = 
  let rec sortUtil acc rev l =
    match l, rev with
    | [], true -> acc |> List.rev
    | [], false -> acc |> List.rev |> sortUtil [] true
    | x::y::tl, _ when x > y -> sortUtil (y::acc) false (x::tl)
    | hd::tl, _ -> sortUtil (hd::acc) rev tl
  sortUtil [] true l

On the other side, you can implement the same algorithm using mutable arrays. This will be more efficient and in F# you can work with arrays too if you want. The following function creates a copy of the array and sorts it.

let sort (arr:'a[]) = 
  let arr = arr |> Array.copy
  let swap i j = let tmp = arr.[i] in arr.[i] <- arr.[j]; arr.[j] <- tmp
  for i = arr.Length - 1 downto 0 do
    for j = 1 to i do
      if (arr.[j - 1] > arr.[j]) then swap (j-1) j
  arr

Tomas