// splitList the input list let splitList 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
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 = splitList (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 (* val randomList : int list = [0; 0; 0; 1; 3; 0; 2; 1; 6; 4; 2; 1; 0; 7; 1; 4; 13; 4; 17; 15; 18; 7; 7; 15; 4; 24; 20; 9; 13; 1; 13; 8; 1; 9; 25; 25; 8; 19; 36; 19; 29; 27; 25; 25; 22; 18; 35; 17; 14; 47; 11; 16; 17; 41; 16; 8; 3; 34; 26; 54; 22; 2; 43; 51; 6; 64; 7; 50; 53; 28; 4; 22; 22; 36; 4; 18; 56; 56; 12; 60; 16; 32; 2; 41; 68; 11; 80; 21; 86; 53; 58; 58; 5; 2; 10; 65; 92; 76; 48; 51; ...] val res : int list = [0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 2; 2; 2; 2; 2; 2; 2; 2; 2; 2; 2; 2; 2; 2; 2; 3; 3; 3; 3; 3; 3; 3; 3; 3; 4; 4; 4; 4; 4; 4; 4; 4; 4; 4; 4; 4; 4; 4; 4; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 6; 6; 6; 6; 6; 6; 6; 6; 7; 7; 7; 7; 7; 7; 7; 7; 7; 7; 7; 7; 7; 7; 7; ...] *)