Last active
October 5, 2016 05:13
-
-
Save marioeguiluz/374a34d498fdafa2c657 to your computer and use it in GitHub Desktop.
Merge Sort Swift
This file contains hidden or 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
//Merge Sort | |
func mergeSort<T:Comparable>(_ unsortedArray:Array<T>)->Array<T>{ | |
var unsortedArray = unsortedArray | |
if unsortedArray.count < 2 { | |
return unsortedArray | |
} | |
let pivot:Int = unsortedArray.count/2 | |
let leftArray:Array<T> = Array(unsortedArray[0..<pivot]) | |
let rightArray:Array<T> = Array(unsortedArray[pivot..<unsortedArray.count]) | |
return mergeArrays(mergeSort(leftArray), B: mergeSort(rightArray)) | |
} | |
func mergeArrays<T:Comparable>(_ A:Array<T>,B:Array<T>)->Array<T>{ | |
let leftIndex = 0 | |
let rightIndex = 0 | |
var orderedArray:Array<T> = [] | |
while leftIndex<A.count && rightIndex<B.count { | |
if A[leftIndex] < B[rightIndex] { | |
orderedArray.append(A[leftIndex+1]) | |
} | |
else if A[leftIndex] > B[rightIndex] { | |
orderedArray.append(B[rightIndex+1]) | |
} | |
else { | |
orderedArray.append(A[leftIndex+1]) | |
orderedArray.append(B[rightIndex+1]) | |
} | |
} | |
orderedArray = orderedArray + Array(A[leftIndex..<A.count]) | |
orderedArray = orderedArray + Array(B[rightIndex..<B.count]) | |
return orderedArray | |
} |
How does Swift's Array constructor work when fed two indices in an existing array? If it copies each value into a new array surely that ruins the nlogn time complexity that merge sort should have no?
Curious to know the time and space complexity when using this method of creating a new array rather than dealing with indices in the existing array.
Thanks
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Updated for Swift 3.0 with Generics