Give an algorithm that determines the number of inversions in any permutation on n elements in O(nlgn) worst-case time.

///Merge Sort. Θ(nlgn)
func mergeInversionsSort<T: Comparable>(array: inout [T]) -> Int {
    return _mergeInversionsSort(array: &array, lower: 0, upper: array.count-1);
}

///Inner representation
func _mergeInversionsSort<T: Comparable>(array: inout [T], lower: Int, upper: Int) -> Int {
    guard lower < upper else { return 0 }
    //Note：upper+lower NOT upper-lower
    let divider = (upper+lower)/2
    var count = 0
    count += _mergeInversionsSort(array: &array, lower: lower, upper: divider)
    count += _mergeInversionsSort(array: &array, lower: divider+1, upper: upper)
    count += mergeInversions(of: &array, lower: lower, divider: divider, upper: upper)
    return count;
}

///Merge Inversion. Θ(n)
func mergeInversions<T: Comparable>(of array:inout [T], lower:Int, divider:Int, upper:Int) -> Int {
    var count = 0
    let prefix = Array(array[lower...divider])
    let suffix = Array(array[divider+1...upper])
    //Note：k = lower NOT k = 0
    var i = 0, j = 0, k = lower
    while i<prefix.count, j<suffix.count {
        if prefix[i] <= suffix[j] {
            array[k] = prefix[i]
            i += 1
        } else {
            array[k] = suffix[j]
            j += 1
            //Core inversions statistics
            count += prefix.count-i
        }
        k += 1
    }
    if i == prefix.count {
        while j < suffix.count {
            array[k] = suffix[j]
            k += 1
            j += 1
        }
    } else {
        while i < prefix.count {
            array[k] = prefix[i]
            k += 1
            i += 1
        }
    }
    return count
}

var s = try Int.randomArray()
mergeInversionsSort(array: &s)