I would appreciate some quick comments on this basic mergesort code. Am I missing a big block in the langage?
First solution
open System
open System.Windows
open System.Collections.Generic
let shuffle (l:'a array) =
let ileft = LinkedList<int>(seq { 0 .. (l.Length - 1)})
let rec pick (ar:'a array) r =
match ileft.Count with | 0 -> r
| n -> let ik = ileft |> Seq.nth (rnd.Next(n))
ileft.Remove(ik) |> ignore
pick ar (ar.[ik]::r)
pick l []
let rec merge (ar1:'a array) (ar2:'a array) =
let rec index (islastfromAr1, ilast, jlast) = seq {
let inext, jnext = ilast + 1, jlast + 1
match inext < ar1.Length, jnext < ar2.Length with
| true , true -> let indexnext = if ar1.[inext] < ar2.[jnext] then
(true, inext, jlast)
else
(false, ilast, jnext)
yield Some(indexnext)
yield! index indexnext
| false, true -> let indexnext = (false, ilast, jnext)
yield Some(indexnext)
yield! index indexnext
| true , false -> let indexnext = (true, inext, jlast)
yield Some(indexnext)
yield! index indexnext
| false, false -> yield None
}
let mergeindex = index (false, -1, -1)
[for (formar1, i,j) in mergeindex |> Seq.choose (id) -> if formar1 then ar1.[i] else ar2.[j] ]
and mergesort = function
| [| |] -> [||]
| [|a|] -> [|a|]
| ar -> let ar1 = ar.[0 .. ar.Length / 2 - 1]
let ar2 = ar.[ar.Length / 2 .. ar.Length - 1]
merge (mergesort ar1) (mergesort ar2) |> List.toArray
let testval = ( [|1 .. 100|] |> shuffle |> List.toArray)
let test4 = mergesort testval
Second solution
a shorter, mutable state version of it
let rec mergemutable (ar1:'a array) (ar2:'a array) =
let inext, jnext = ref 0 , ref 0
[ for k in [1 .. (ar1.Length + ar2.Length)] ->
match !inext < ar1.Length, !jnext < ar2.Length with
| true , true -> if ar1.[!inext] < ar2.[!jnext] then
inext := !inext + 1
ar1.[!inext - 1]
else
jnext := !jnext + 1
ar2.[!jnext - 1]
| false, true -> jnext := !jnext + 1
ar2.[!jnext - 1]
| true , false -> inext := !inext + 1
ar1.[!inext - 1 ]
| _ -> failwith "should not happen"
]
and mergesortmutable = function
| [| |] -> [||]
| [|a|] -> [|a|]
| ar -> let ar1 = ar.[0 .. ar.Length / 2 - 1]
let ar2 = ar.[ar.Length / 2 .. ar.Length - 1]
(mergemutable (mergesortmutable ar1) (mergesortmutable ar2) ) |> List.toArray
let testmutable = mergesortmutable ( [|1 .. 100|] |> shuffle |> List.toArray)
It is much faster.
Third solution
Another one with no extraneous allocations
let mergesortmutable2 ar =
let mutable sarlast = ref (Array.copy ar)
let mutable sarcurr = ref (Array.copy ar)
let rec mergemutable (sarcurr:'a array ref) (sarlast:'a array ref) s (s1,e1) (s2,e2) =
let mutable inext, jnext = s1 , s2
for k in [1 .. ((e1-s1+1) + (e2-s2+1)) ] do
match inext <= e1, jnext <= e2 with
| true , true -> if (!sarlast).[inext] < (!sarlast).[jnext] then
(!sarcurr).[(s+(k-1))] <- (!sarlast).[inext]
inext <- inext + 1
else
(!sarcurr).[(s+(k-1))] <- (!sarlast).[jnext]
jnext <- jnext + 1
| false, true -> (!sarcurr).[(s+(k-1))] <- (!sarlast).[jnext]
jnext <- jnext + 1
| true , false -> (!sarcurr).[(s+(k-1))] <- (!sarlast).[inext]
inext <- inext + 1
| _ -> failwith "should not happen"
(s1,e2)
and mergesortmutable (sarcurr:'a array ref) (sarlast:'a array ref) (s,e) =
match s, e with
| s, e when s >= e -> s,e
| _ -> let m = (e-s+1) / 2
let ar1 = (mergesortmutable sarlast sarcurr (s, s + m - 1))
let ar2 = (mergesortmutable sarlast sarcurr (s + m, e))
let ret = mergemutable sarcurr sarlast s ar1 ar2
ret
do mergesortmutable sarcurr sarlast (0, ar.Length - 1) |> ignore
!sarcurr