CODEWITHSUNDEEP
f#
Caroline Maina
Caroline Maina

Reputation: 93

Merge sort code in F# not sorting

Im trying to write a merge sort code. its printing though not sorting. What could I be doing wrong? 

let rec mergePm xs ys =
    match (xs, ys) with
    | [], _ -> ys
    | _,[] -> xs
    | x::xs, y::ys ->
        if x < y then x :: mergePm xs (y::ys)
        else y :: mergePm (x::xs) ys

let rec msortPm 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 mergePm (msortPm ys) (msortPm zs)

printfn "%A" (msortPm[1,2,6,5])

Upvotes: 2

Views: 99

Answers (1)

Fyodor Soikin
Fyodor Soikin

Reputation: 80744

You're using the wrong list syntax.

When you say [1,2,6,5], you're not making a list of four elements, but rather a list one one element, and that element is a tuple of four numbers.

In F# list elements are separated by either a new line or a semicolon.

This should work fine:

printfn "%A" (msortPm[1;2;6;5])

Additionally, I'd like to point out that List.length does a full pass of the list (since F# lists are immutable singly linked lists), so that slows down your algorithm. It's better to pattern-match on empty list and list of one element:

let rec msortPm xs = match xs with
    | [] | [_] -> xs
    | _ ->
        let n = sz / 2
        let ys = xs. [0..n-1]
        let zs = xs.[n..sz-1]
        mergePm (msortPm ys) (msortPm zs)

(also notice how in after let is optional in F#)

Upvotes: 4

Related Questions