Skip to content

Instantly share code, notes, and snippets.

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] {
else if A[leftIndex] > B[rightIndex] {
else {
orderedArray = orderedArray + Array(A[leftIndex..<A.count])
orderedArray = orderedArray + Array(B[rightIndex..<B.count])
return orderedArray

This comment has been minimized.

Copy link
Owner Author

@marioeguiluz marioeguiluz commented Sep 21, 2016

Updated for Swift 3.0 with Generics


This comment has been minimized.

Copy link

@Anteloper Anteloper 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.


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.