Write mergesort in F#: A merge sort works as follows recursively: (1) Divide the

Question

Write mergesort in F#: A merge sort works as follows recursively: (1) Divide the unsorted list into two sublists; (2) Sort the two sublists; (3) Merge two sorted sublists to produce a new sorted list. Use the split function in Homework #3 to accomplish step (1); Write a recursive function merge to merge to sorted sublists into one sorted list to do (3); Write a recursive function mergesort, which uses the split function to obtain two unsorted sublists from one unsorted list, recursively calls itself on the two unsorted sublists, and then uses merge to get the final sorted list.

Explanation / Answer

// Merge Sort in F#

// The input list splitList
let s_list divSize lst =
let rec splitAcc divSize cont = function
    | [] -> cont([],[])
    | l when divSize = 0 -> cont([], l)
    | h::t -> splitAcc (divSize-1) (fun acc -> cont(h::fst acc, snd acc)) t
splitAcc divSize (fun x -> x) lst

// merge two sub-lists
let merge l r =
let rec mergeCont cont l r =
    match l, r with
    | l, [] -> cont l
    | [], r -> cont r
    | hl::tl, hr::tr ->
      if hl<hr then mergeCont (fun acc -> cont(hl::acc)) tl r
      else mergeCont (fun acc -> cont(hr::acc)) l tr
mergeCont (fun x -> x) l r

// Sorting via merge
let mergeSort lst =
let rec mergeSortCont lst cont =
    match lst with
    | [] -> cont([])
    | [x] -> cont([x])
    | l -> let left, right = s_list (l.Length/2) l
           mergeSortCont left (fun accLeft ->
           mergeSortCont right (fun accRight -> cont(merge accLeft accRight)))
mergeSortCont lst (fun x -> x)

// initialization function
let randFunc =
let rnd = (new System.Random(int System.DateTime.Now.Ticks)).Next
rnd

// create a random list
let randomList = List.init 1000000 randFunc

// result:
let res = mergeSort randomList

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.