mergesort.swift

import Darwin  //.C.stdlib

// updated for Swift 2.0 beta4

private func merge<T: Comparable>(a: ArraySlice<T>, _ b: ArraySlice<T>, mergeInto acc: ArraySlice<T> = []) -> ArraySlice<T> {
    guard let aF = a.first, bF = b.first else {
        return acc + a + b
    }
    return aF < bF
        ? merge(dropFirst(a), b, mergeInto: acc + [aF])
        : merge(dropFirst(b), a, mergeInto: acc + [bF])
}

private func divide<T: Comparable>(a: ArraySlice<T>) -> ArraySlice<T> {
    let i = a.count / 2
    guard i > 0 else { return a }
    let (left, right) = (a[0..<i], a[i..<a.count])
    return merge(divide(left), divide(right))
}

public func mergesort<T: Comparable>(a: Array<T>) -> ArraySlice<T> {
    return divide(ArraySlice(a))
}

let unsorted = (1...100).map{_ in arc4random_uniform(200) }
let sorted = mergesort(unsorted)

print(sorted)