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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment