mergesort.swift

import Foundation

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

private func divide<T: Comparable>(a: ArraySlice<T>) -> ArraySlice<T> {
  
  let c = a.count / 2
  
  return c == 0 ? a : merge(divide(a[0..<c]), divide(a[c..<a.count]))
  
}

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

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

println(sorted)