Skip to content

Instantly share code, notes, and snippets.

@go-cristian
Last active August 18, 2016 11:48
Show Gist options
  • Save go-cristian/4ef98e21f3b62aba2c68808eb3e99c92 to your computer and use it in GitHub Desktop.
Save go-cristian/4ef98e21f3b62aba2c68808eb3e99c92 to your computer and use it in GitHub Desktop.
Merge sort implementation on Swift
import Foundation
/**
Sorts an array using the merge arrangement, which relays in order the left & right half arrays in a major set of elements. giving a complexity of O(n log n).
- Returns: An ordered array.
*/
func mergeSort(arr:[Int]) -> [Int] {
guard arr.count > 1 else {return arr}
let middle: Int = Int(ceil(Double(arr.count/2)))
let left: [Int] = mergeSort(Array(arr[0..<arr.count/2]))
let right: [Int] = mergeSort(Array(arr[middle..<arr.count]))
return merge(left, right)
}
/**
Traverses both arrays and merge the result in an orderer array, supposing left & right are ordered.
- Parameter left: An ordered array to be merged.
- Parameter right: An ordered array to be merged.
- Returns: An ordered array with complexity O(n).
*/
func merge(left: [Int], _ right: [Int]) -> [Int]{
var leftIndex = 0
var rightIndex = 0
var result: [Int] = []
//is append available on right or left
while leftIndex<left.count || rightIndex<right.count {
//apennd can happen on left side
if leftIndex<left.count &&
(rightIndex>=right.count || left[leftIndex] < right[rightIndex]) {
result.append(left[leftIndex])
leftIndex += 1
} else {
result.append(right[rightIndex])
rightIndex += 1
}
}
return result
}
let array = [5,6,4,3,2,1]
print(mergeSort(array))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment