Created
February 5, 2013 23:59
-
-
Save thelinked/4718921 to your computer and use it in GitHub Desktop.
F# merge sort using continuation passing style
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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