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
// Divide the unsorted list into two sublists
let s_list size lst =
let rec splitAcc size cont = function
    | [] -> cont([],[])
    | l when size = 0 -> cont([], l)
    | h::t -> splitAcc (size-1) (fun acc -> cont(h::fst acc, snd acc)) t
splitAcc size (fun x -> x) lst

// Merge two sorted sublists to produce a new sorted list
// 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

// Sort the two sublists
// 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 1000 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.