mergesort.fsx

//pema99 - Merge sort implementation - 23/09/2021

let rec merge op l r =
  match l, r with
  | [], _ -> r
  | _, [] -> l
  | lh::lt, rh::rt  -> 
    if op lh rh then lh :: merge op lt r
    else rh :: merge op l rt

let rec mergeSort op lst =
  match lst with
  | [_] | [] -> lst
  | _ -> let l, r = List.splitAt (List.length lst / 2) lst 
         merge op (mergeSort op l) (mergeSort op r)

let mergeSortAscending = mergeSort (<)
let mergeSortDescending = mergeSort (>)

printfn "%A" (mergeSortAscending [31;41;59;26;41;58])
printfn "%A" (mergeSortDescending [31;41;59;26;41;58])