Sort Algorithms in F#

Further to the earlier post about functional programming, I've been doing a little more playing around with F#. This week, I was looking into sorts. I found this quick sort snippet particularly cool:

let quicksortM M fn a =
  let N = Array.length a - 1
  let mutable stack = [0,0]
  let mutable l = 0
  let mutable r = N

  let swap x y =
  let t = a.[ x ]
  a.[ x ] <- a.[ y ]
      a.[ y ] <- t

  let sort3 x y z =
      if a.[ x ] > a.[ y ] then swap x y
      if a.[ x ] > a.[ z ] then swap x z
      if a.[ y ] > a.[ z ] then swap y z

  while stack <> [] do

      let count = (r-l)+1

According to the author,

[this] Quicksort is almost 2x faster than the .NET library sort above 1,000 elements in the random and forward ordered cases

UPDATE:

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 hand, 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