SortedMerged.swift

extension RandomAccessCollection {
  func sortedMerged(
    with otherSorted: [Element],
    areInIncreasingOrder: (Element, Element) -> Bool
  ) -> [Element] where Element: Identifiable {
    let otherIds = Set<Element.ID>(otherSorted.map(\.id))
    var result = [Element]()
    result.reserveCapacity(count + otherSorted.count)
    var currentIndex = startIndex
    var otherIndex = otherSorted.startIndex
    while currentIndex < endIndex, otherIndex < otherSorted.endIndex {
      if areInIncreasingOrder(self[currentIndex], otherSorted[otherIndex]) {
        // Prefer elements from the other collection over elements in the existing collection
        if !otherIds.contains(self[currentIndex].id) {
          result.append(self[currentIndex])
        }
        currentIndex = self.index(after: currentIndex)
      } else {
        result.append(otherSorted[otherIndex])
        otherIndex = otherSorted.index(after: otherIndex)
      }
    }
    // The other sorted array was exhausted, add remaining elements from the existing array
    while currentIndex < endIndex {
      // Prefer elements from the other collection over elements in the existing collection
      if !otherIds.contains(self[currentIndex].id) {
        result.append(self[currentIndex])
      }
      currentIndex = self.index(after: currentIndex)
    }
    // The existing sorted array was exhausted, add remaining elements from the other array
    if otherIndex < otherSorted.endIndex {
      result.append(contentsOf: otherSorted[otherIndex...])
    }
    return result
  }
}