Skip to content

Instantly share code, notes, and snippets.

@tbhaxor
Created June 19, 2018 11:10
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save tbhaxor/cdba63ac2050de58b12a716ddadd38ee to your computer and use it in GitHub Desktop.
merge sort
import Foundation
func sort(_ arr1: [Int], _ arr2: [Int]) -> [Int] {
var c = Array<Int>()
var arr1 = arr1
var arr2 = arr2
let c1 = arr1.count
let c2 = arr2.count
if c1 > c2 {
for _ in 0..<c2 {
if arr1[0] < arr2[0] {
c.append(arr1[0])
arr1.removeFirst()
} else {
c.append(arr2[0])
arr2.removeFirst()
}
}
for leftItem in arr1 {
c.append(leftItem)
}
} else{
for _ in 0..<c1 {
if arr1[0] < arr2[0] {
c.append(arr1[0])
arr1.removeFirst()
} else {
c.append(arr2[0])
arr2.removeFirst()
}
}
for leftItem in arr2 {
c.append(leftItem)
}
}
return c
}
func mergeSort(_ arr: [Int]) -> [Int] {
guard arr.count > 1 else {
return arr
}
let middleIndex = arr.count / 2
let leftArray = mergeSort(Array(arr[0..<middleIndex]))
let rightArray = mergeSort(Array(arr[middleIndex..<arr.count]))
return sort(leftArray, rightArray)
}
var testCase1 = [1, 2, 3, 4, 5, 6, 7]
var testCase2 = [5, 6, 4, 3, 1, 0, 2]
print(mergeSort(testCase1))
print(mergeSort(testCase2))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment