5 people like it.
Like the snippet!
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:
|
// spilitList the input list
let spilitList divSize lst =
let rec spilitAcc divSize cont = function
| [] -> cont([],[])
| l when divSize = 0 -> cont([], l)
| h::t -> spilitAcc (divSize-1) (fun acc -> cont(h::fst acc, snd acc)) t
spilitAcc 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<hr then mergeCont (fun acc -> 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 = spilitList (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 spilitList : divSize:int -> lst:'a list -> 'a list * 'a list
Full name: Script.spilitList
val divSize : int
val lst : 'a list
val spilitAcc : (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()
(+0 other overloads)
System.DateTime(ticks: int64) : unit
(+0 other overloads)
System.DateTime(ticks: int64, kind: System.DateTimeKind) : unit
(+0 other overloads)
System.DateTime(year: int, month: int, day: int) : unit
(+0 other overloads)
System.DateTime(year: int, month: int, day: int, calendar: System.Globalization.Calendar) : unit
(+0 other overloads)
System.DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int) : unit
(+0 other overloads)
System.DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, kind: System.DateTimeKind) : unit
(+0 other overloads)
System.DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, calendar: System.Globalization.Calendar) : unit
(+0 other overloads)
System.DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, millisecond: int) : unit
(+0 other overloads)
System.DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, millisecond: int, kind: System.DateTimeKind) : unit
(+0 other overloads)
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 Head : '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
More information