CountInversions.swift

import Foundation

/**
 Counts the number of inversions on the given array.
 - Returns: the number of the inversions.
 */
func countInversions(arr:[Int]) -> Int {
    guard arr.count > 1 else {return 0}
    let middle: Int = Int(ceil(Double(arr.count/2)))
    let left: [Int] = Array(arr[0..<arr.count/2])
    let right: [Int] = Array(arr[middle..<arr.count])
    let leftInversions: Int = countInversions(left)
    let rightInversions: Int = countInversions(right)
    let mixed: Int = countInversionsMerge(left, right)
    return leftInversions + rightInversions + mixed
}

func countInversionsMerge(left: [Int], _ right: [Int]) -> Int{
    var leftIndex = 0
    var rightIndex = 0
    var inversions: Int = 0

    while leftIndex<left.count && rightIndex<right.count {
        if left[leftIndex]<right[rightIndex]{
            leftIndex += 1
        } else {
            inversions += left.count - leftIndex
            rightIndex += 1
        }
    }
    return inversions
}


let array = [1,3,5,2,4,6]
print(countInversions(array))