Skip to content

Instantly share code, notes, and snippets.

@marioeguiluz
Last active October 5, 2016 05:13
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save marioeguiluz/374a34d498fdafa2c657 to your computer and use it in GitHub Desktop.
Save marioeguiluz/374a34d498fdafa2c657 to your computer and use it in GitHub Desktop.
Merge Sort Swift
//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
}
@marioeguiluz
Copy link
Author

Updated for Swift 3.0 with Generics

@Anteloper
Copy link

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