Rewrite msort, so it uses pattern matching in F#

Question

The code underneath is the code for mergesort in f# and I have to rewrite it, so it uses pattern matching.

let rec msort xs =
let sz = List.length xs
        if sz < 2 then xs
        else let n = sz / 2
            let ys = xs.[0..n-1]
            let zs = xs.[n..sz-1]
            in merge (msort ys) (msort zs)

So far I've gotten is to here:

let rec msort (vs: int list) =
    let sz = List.length xs
    match xs with 
    | List.length < 2 -> vs 
    | _ -> 
        let n = sz / 2
        let ys = xs.[0..n-1]
        let zs = xs.[n..sz-1]
        in merge (msort ys) (msort zs)

I can't seem to figure out a better way. Is there anyone who can help me on my way?

what exactly are you having an issue with? You could study [this question on Code Review](https://codereview.stackexchange.com/questions/37904/merge-sort-program). — s952163, Jan 22 '18 at 01:53

Aaron M. Eshbach · Accepted Answer · 2018-01-22T04:25:04.203

I would probably do it like this:

let rec msort (values: int list) =
    let n = values.Length / 2
    if n = 0 
    then values
    else let rec merge (xs: int list) (ys: int list) =
             match (xs, ys) with
             | ([], ys) -> ys
             | (xs, []) -> xs
             | (x :: xs1, y :: ys1) ->
                  if x < y
                  then x :: merge xs1 ys
                  else y :: merge xs ys1        

         let (first, second) = values |> List.splitAt n
         merge (msort first) (msort second)

Pattern matching isn't too useful on the initial logic (length of the list, early exits for length 0 and 1), but I think it makes it more readable when matching the cases for the sub-lists after the split. Even so, there's only one if/then in the msort portion and it could be replaced with a pattern match if you really wanted to:

let rec msort (values: int list) =
    match values.Length / 2 with
    | 0 -> values
    | n -> 
        let rec merge (xs: int list) (ys: int list) =
            match (xs, ys) with
            | ([], ys) -> ys
            | (xs, []) -> xs
            | (x :: xs1, y :: ys1) ->
                if x < y
                then x :: merge xs1 ys
                else y :: merge xs ys1        

        let (first, second) = values |> List.splitAt n
        merge (msort first) (msort second)

This leaves only the if/then for x<y in the merge implementation, and I wouldn't change that.

score 1 · Answer 2 · answered Jan 22 '18 at 09:09

Almost the same, but I propose a custom split:

let split2 (li: int list) =
    let n = (List.length li) / 2
    let rec looprec (len: int) (l1: int list) (l2: int list) =
         if len > 0 then
            match l1 with 
               | x::tail -> looprec (len-1) tail (x::l2)
               | _ -> (List.rev l2, l1)               
         else 
           (List.rev l2, l1)
     in looprec n li []

let rec merge (l1: int list) (l2: int list) =
    match (l1,l2) with
        | (x,[]) -> x
        | ([],y) -> y
        | (x::tx,y::ty) ->
            if x <= y 
            then x::merge tx l2
            else y::merge l1 ty

let rec msort (li: int list) = 
    match li with
        | [] -> []
        | [x] -> [x]
        | _ -> let (l1,l2) = split2 li
               in merge (msort l1) (msort l2)

let d=  msort [3;20;12]

printfn "%A" d

Rewrite msort, so it uses pattern matching in F#

2 Answers2