Inversions.fs

// Inversions count. Based on merge sort

let rec merge (left: list<int>) (right: list<int>) =
    match left, right with
    | [], [] -> ([], bigint 0)
    | _, [] -> (left, bigint 0)
    | [], _ -> (right, bigint 0)
    | headLeft::tailLeft, headRight::tailRight when headLeft > headRight ->
        let (merged, inv) = merge left tailRight
        (headRight::merged, inv + bigint left.Length)
    | h1::t1, h2::t2 when h1 <= h2->
        let (merged, inv) = merge t1 right
        (h1::merged, inv)

let sort (a: list<int>) =
    let rec sortInner (a: list<int>) x1 xn = 
        match xn - x1 with
            | some when some <= 0 -> ([a.[x1]], bigint 0)
            | _ -> 
                let leftEnd = x1 + (xn - x1 + 1)/2 - 1
                let (left, invLeft) = sortInner a x1 leftEnd
                let (right, invRight) = sortInner a (leftEnd + 1) xn
                let (merged, invSplit) = merge left right
                (merged, invLeft + invRight + invSplit)

    sortInner a 0 (a.Length-1)