Discussion on: Making Sense of Merge Sort [Part 1]

[Ben Halpern]

Heck yes!

[Vaidehi Joshi]

Yes! I totally support this decision, Prash. And would love to see your implementation when you're done :)

[Prash]

OK, I finally got round to it. This is an implementation in my language of choice, F#. Note that I didn't read the JS implementation. This is purely based on your description of recursive splitting and merging, and so there is no mutation here. Just a lot of building up of arrays and lists, so it's probably not very efficient. It was fun to write, though!

let split xs =
    let mid = Array.length xs / 2
    (xs.[0 .. mid - 1], xs.[mid .. xs.Length - 1])

let rec merge xs ys acc =
    match xs, ys with
    | []      , []       -> List.rev acc
    | x :: xs', []
    | []      , x :: xs' -> merge xs' [] (x :: acc)
    | x :: xs', y :: ys' ->
        if x < y then merge xs' ys  (x :: acc)
        else          merge xs  ys' (y :: acc)

let rec mergeSort xs =
    match split xs with
    | [| |], [| |] -> [ ]
    | [| |], [|x|]
    | [|x|], [| |] -> [x]
    | [|x|], [|y|] -> merge [x] [y] []
    | xs   , ys    -> merge (mergeSort xs) (mergeSort ys) []