5 people like it.

# Merge Sort on List

Merge Sort falls into 'Divide and Conquer' problem solving technique and it is a stable sorting. The worst case of running time is (nlogn). This implementation below follows the two abstract steps to achieve Merge Sort, i.e., * Recursively divide input list into two sub-lists. * Repeatedly merge the sub-lists.

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: ``` ``````// 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; ...] *) ``````
val splitList : divSize:int -> lst:'a list -> 'a list * 'a list

Full name: Script.splitList
val divSize : int
val lst : 'a list
val splitAcc : (int -> ('b list * 'b list -> 'c) -> 'b list -> 'c)
val cont : ('b list * 'b list -> 'c)
val l : 'b list
val h : 'b
val t : 'b list
val acc : 'b list * 'b list
val fst : tuple:('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst
val snd : tuple:('T1 * 'T2) -> 'T2

Full name: Microsoft.FSharp.Core.Operators.snd
val x : 'a list * 'a list
val merge : l:'a list -> r:'a list -> 'a list (requires comparison)

Full name: Script.merge
val l : 'a list (requires comparison)
val r : 'a list (requires comparison)
val mergeCont : (('b list -> 'c) -> 'b list -> 'b list -> 'c) (requires comparison)
val cont : ('b list -> 'c) (requires comparison)
val l : 'b list (requires comparison)
val r : 'b list (requires comparison)
val hl : 'b (requires comparison)
val tl : 'b list (requires comparison)
val hr : 'b (requires comparison)
val tr : 'b list (requires comparison)
val acc : 'b list (requires comparison)
val x : 'a list (requires comparison)
val mergeSort : lst:'a list -> 'a list (requires comparison)

Full name: Script.mergeSort
val lst : 'a list (requires comparison)
val mergeSortCont : ('b list -> ('b list -> 'c) -> 'c) (requires comparison)
val lst : 'b list (requires comparison)
val x : 'b (requires comparison)
val left : 'b list (requires comparison)
val right : 'b list (requires comparison)
property List.Length: int
val accLeft : 'b list (requires comparison)
val accRight : 'b list (requires comparison)
val randFunc : (int -> int)

Full name: Script.randFunc
val rnd : (int -> int)
namespace System
Multiple items
type Random =
new : unit -> Random + 1 overload
member Next : unit -> int + 2 overloads
member NextBytes : buffer:byte[] -> unit
member NextDouble : unit -> float

Full name: System.Random

--------------------
System.Random() : unit
System.Random(Seed: int) : unit
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
Multiple items
type DateTime =
struct
new : ticks:int64 -> DateTime + 10 overloads
member Add : value:TimeSpan -> DateTime
member AddDays : value:float -> DateTime
member AddHours : value:float -> DateTime
member AddMilliseconds : value:float -> DateTime
member AddMinutes : value:float -> DateTime
member AddMonths : months:int -> DateTime
member AddSeconds : value:float -> DateTime
member AddTicks : value:int64 -> DateTime
member AddYears : value:int -> DateTime
...
end

Full name: System.DateTime

--------------------
System.DateTime()
System.DateTime(ticks: int64) : unit
System.DateTime(ticks: int64, kind: System.DateTimeKind) : unit
System.DateTime(year: int, month: int, day: int) : unit
System.DateTime(year: int, month: int, day: int, calendar: System.Globalization.Calendar) : unit
System.DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int) : unit
System.DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, kind: System.DateTimeKind) : unit
System.DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, calendar: System.Globalization.Calendar) : unit
System.DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, millisecond: int) : unit
System.DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, millisecond: int, kind: System.DateTimeKind) : unit
property System.DateTime.Now: System.DateTime
property System.DateTime.Ticks: int64
val randomList : int list

Full name: Script.randomList
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val init : length:int -> initializer:(int -> 'T) -> 'T list

Full name: Microsoft.FSharp.Collections.List.init
val res : int list

Full name: Script.res