Merge Sort. Θ(nlgn)

///Merge Sort. O(nlgn)
func mergeSort<T: Comparable>(array: inout [T]) {
    _mergeSort(array: &array, lower: 0, upper: array.count-1);
}

///Inner representation
func _mergeSort<T: Comparable>(array: inout [T], lower: Int, upper: Int) {
    guard lower < upper else { return }
    //Note：upper+lower NOT upper-lower
    let divider = (upper+lower)/2
    _mergeSort(array: &array, lower: lower, upper: divider)
    _mergeSort(array: &array, lower: divider+1, upper: upper)
    merge(array: &array, lower: lower, divider: divider, upper: upper)
}

///Core merge algorithm
func merge<T: Comparable>(array: inout [T], lower: Int, divider: Int, upper: Int) {
    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
        }
        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
        }
    }
}

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