Skip to content

Instantly share code, notes, and snippets.

@thelinked
Created February 5, 2013 23:59
Show Gist options
  • Save thelinked/4718921 to your computer and use it in GitHub Desktop.
Save thelinked/4718921 to your computer and use it in GitHub Desktop.
F# merge sort using continuation passing style
let split input =
let n = ((List.length input)/2)
let rec splitHelper cur cont = function
| head::tail when cur < n ->
splitHelper (cur+1) (fun acc ->
cont (head::acc)) tail
| rest -> cont [], rest
splitHelper 0 id input
let merge xs ys =
let rec mergeHelper xs ys cont =
match xs,ys with
| [],l | l,[] -> cont l
| x::xtail, y::ytail ->
if x < y then (mergeHelper xtail ys (fun acc -> cont (x::acc)))
else (mergeHelper xs ytail (fun acc -> cont (y::acc)))
mergeHelper xs ys id
let sort input =
let rec sortHelper input size cont =
match size with
| 0 | 1 -> cont input
| _ ->
let x,y = split input
(sortHelper x (List.length x) (fun accL ->
(sortHelper y (List.length y) (fun accR ->
cont (merge accL accR)))))
sortHelper input (List.length input) id
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment