Skip to content

Instantly share code, notes, and snippets.

@avdwerff
Last active February 1, 2016 19:05
Show Gist options
  • Save avdwerff/da433f6752078cbce91b to your computer and use it in GitHub Desktop.
Save avdwerff/da433f6752078cbce91b to your computer and use it in GitHub Desktop.
extension Array where Element: Comparable {
func mergeSort() -> [Element] {
if count <= 1 { return self }
else {
let left = Array(self[0 ..< count/2])
let right = Array(self[count/2 ..< count])
return merge(left.mergeSort(), right: right.mergeSort())
}
}
func merge<T: Comparable>(var left:[T], var right:[T]) -> [T]{
var list:[T] = []
while left.count > 0 && right.count > 0 {
if left[0] <= right[0] {
list.append(left[0])
left.removeFirst()
}
else {
list.append(right[0])
right.removeFirst()
}
}
list.appendContentsOf(left)
list.appendContentsOf(right)
return list
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment