4
\$\begingroup\$

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
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I'd put the code that does the split in a separate function. Though something about your merge code rubs me the wrong way. \$\endgroup\$ Jun 17, 2012 at 5:00
  • \$\begingroup\$ i also wonder if that is not the kind of stuff where one should use mutable variable. \$\endgroup\$
    – nicolas
    Jun 17, 2012 at 7:36
  • 1
    \$\begingroup\$ the array being a ref type already, no need to enclose it in a ref \$\endgroup\$
    – nicolas
    Jun 18, 2012 at 8:05
  • 2
    \$\begingroup\$ Have you googled "f# merge sort"? Here is a particularly good one. \$\endgroup\$
    – Daniel
    Jun 18, 2012 at 15:19

1 Answer 1

3
\$\begingroup\$

I'm just learning F# myself, but here is what I currently notice:

  1. Your merge function is very large. It should be split into multiple small functions that are responsible for a single action.

  2. match is preferred to if:

if ar1.[inext] < ar2.[jnext] then
    (true, inext, jlast)
else
    (false, ilast, jnext)

can be written as:

match ar1.[inext] with
| i when i < ar2.[jnext] -> (true, inext, jlast)
| _ -> (false, ilast, jnext)
  1. islastfromAr1 is never used. This parameter can probably be removed.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.