Concurrent merge sort ported from the Swift Algorithm Club site

concurrent_merge_sort_algorithm_club.swift

// 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)
}