Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Concurrent merge sort ported from the Swift Algorithm Club site
// Ported from https://www.raywenderlich.com/741-swift-algorithm-club-swift-merge-sort
func mergeSort<T: Comparable>(_ array: [T]) async -> [T] {
guard array.count > 1 else { return array }
let middleIndex = array.count / 2
async let leftArray = await mergeSort(Array(array[0..<middleIndex]))
async let rightArray = await mergeSort(Array(array[middleIndex..<array.count]))
return merge(await leftArray, await rightArray)
}
func merge<T: Comparable>(_ left: [T], _ right: [T]) -> [T] {
var leftIndex = 0
var rightIndex = 0
var orderedArray: [T] = []
while leftIndex < left.count && rightIndex < right.count {
let leftElement = left[leftIndex]
let rightElement = right[rightIndex]
if leftElement < rightElement {
orderedArray.append(leftElement)
leftIndex += 1
} else if leftElement > rightElement {
orderedArray.append(rightElement)
rightIndex += 1
} else {
orderedArray.append(leftElement)
leftIndex += 1
orderedArray.append(rightElement)
rightIndex += 1
}
}
while leftIndex < left.count {
orderedArray.append(left[leftIndex])
leftIndex += 1
}
while rightIndex < right.count {
orderedArray.append(right[rightIndex])
rightIndex += 1
}
return orderedArray
}
func getRandomArray(n: Int) -> [Int] {
var array = [Int]()
for i in 0..<n {
array.append(Int.random(in: 0..<1000))
}
return array
}
func test(n: Int) async {
let array = getRandomArray(n: n)
let sortedArray = await mergeSort(array)
print(sortedArray)
}
runAsyncAndBlock {
await test(n: 1000)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment