Merge Sort of int lists

A basic recursive implementation of merge sort on lists of ints.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19:

let rec MergeSort (input: int list) = 
    
    let Merge (left: int list, right: int list) =
        let rec mergeLists (left: int list, right: int list, output: int list) =
            if left = [] then output@right
            else if right = [] then output@left
            else if left.Head < right.Head then mergeLists (left.Tail, right, output@[left.Head])
            else mergeLists (left, right.Tail, output@[right.Head])
        mergeLists (left, right, [])

    if input.Length = 0 then []
    else if input.Length = 1 then input
    else if input.Length = 2 then
        if input.[0] > input.[1] then [input.[1]; input.[0]]
        else input
    else
        let left = MergeSort (input |> Seq.take (input.Length / 2) |> Seq.toList)
        let right = MergeSort (input |> Seq.skip (input.Length / 2) |> Seq.toList)
        Merge (left, right)

val MergeSort : input:int list -> int list

Full name: Script.MergeSort

val input : int list

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<_>

type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

val Merge : (int list * int list -> int list)

val left : int list

val right : int list

val mergeLists : (int list * int list * int list -> int list)

val output : int list

property List.Head: int

property List.Tail: int list

property List.Length: int

module Seq

from Microsoft.FSharp.Collections

val take : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.take

val toList : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList

val skip : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.skip

Raw view Test code New version

More information

Link:	http://fssnip.net/hN
Posted:	11 years ago
Author:	Bret Colloff
Tags:	merge sort