Last active
August 18, 2016 11:48
-
-
Save go-cristian/4ef98e21f3b62aba2c68808eb3e99c92 to your computer and use it in GitHub Desktop.
Merge sort implementation on Swift
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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