Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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

This comment has been minimized.

Copy link
Owner Author

commented Sep 21, 2016

Updated for Swift 3.0 with Generics

@Anteloper

This comment has been minimized.

Copy link

commented Oct 5, 2016

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
You can’t perform that action at this time.