归并排序（mergeSort）算法示例

MergeSort.swift :

// 泛型函数，可以排序任何遵循 Comparable 协议的元素类型
// 函数接受一个数组作为输入，返回排序后的新数组
public func mergeSort<Element>(_ array: [Element]) -> [Element] where Element: Comparable {
  guard array.count > 1 else {
    return array
  }
  // 递归地对左半部分和右半部分进行排序
  let middle = array.count / 2
  let left = mergeSort(Array(array[..<middle]))
  let right = mergeSort(Array(array[middle...]))
  return merge(left, right)
}

// 合并两个已排序的子数组
private func merge<Element>(_ left: [Element], _ right: [Element]) -> [Element] where Element: Comparable {
  var leftIndex = 0
  var rightIndex = 0
  var result: [Element] = []
  while leftIndex < left.count && rightIndex < right.count {
    let leftElement = left[leftIndex]
    let rightElement = right[rightIndex]
    if leftElement < rightElement {
      result.append(leftElement)
      leftIndex += 1
    } else if leftElement > rightElement {
      result.append(rightElement)
      rightIndex += 1
    } else {
      result.append(leftElement)
      leftIndex += 1
      result.append(rightElement)
      rightIndex += 1
    }
  }
  if leftIndex < left.count {
    result.append(contentsOf: left[leftIndex...])
  }
  if rightIndex < right.count {
    result.append(contentsOf: right[rightIndex...])
  }
  return result
}

这个实现展示了Swift的几个重要特性：

1. 泛型编程：通过使用泛型，该算法可以排序任何 Comparable 类型。
2. 递归：mergeSort 函数通过递归来实现分治策略。
3. 函数式编程：通过将排序过程分解为smaller、可组合的函数。

归并排序的时间复杂度为 O(n log n)，空间复杂度为 O(n)。这是一个稳定的排序算法，适用于大型数据集，特别是在外部排序中很有用。