Mergesort.swift

extension Array {
    var decompose: (head: Element, tail: [Element])? {
        return (count > 0) ? (self[0],tail) : nil
    }
    
    var tail: [Element] {
        return Array(self[1..<count])
    }
    
    func splitAt(n: Int) -> ([Element], [Element]) {
        assert(n >= 0 && n < count)
        return (Array(self[0..<n]), Array(self[n..<count]))
    }
}

func mergeSort<T: Comparable>(input: [T]) -> [T] {
    let half = input.count/2
    if(half == 0) {
        return input
    } else {
        func merge(xs: [T], _ ys: [T]) -> [T] {
            switch (xs, ys) {
            case (let a, _) where a.isEmpty:
                return ys
            case(_, let b) where b.isEmpty:
                return xs
            case (let a, let b):
                let x = a.first!
                let y = b.first!
                if x < y {
                    return [x] + merge(a.tail, b)
                } else {
                    return [y] + merge(a, b.tail)
                }
            }
        }
        let (first, second) = input.splitAt(half)
        return merge(mergeSort(first), mergeSort(second))
    }
}