1 people like it.

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:8 years ago
Author:Bret Colloff
Tags: merge sort