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:

// 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<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 = 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()
   (+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

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/ea
Posted:	11 years ago
Author:	Joel Huang
Tags:	algorithms , merge sort , list