MergeSortedSequence.swift

struct MergeSortedSequence<First: Sequence, Second: Sequence>: Sequence where First.Element == Second.Element {
    var first: First
    var second: Second
    var areInIncreasingOrder: (Element, Element) -> Bool
    
    struct Iterator: IteratorProtocol {
        var first: First.Iterator
        var second: Second.Iterator
        var areInIncreasingOrder: (Element, Element) -> Bool

        enum Peek {
            case first(Element)
            case second(Element)
        }
        var peek: Peek?
        
        mutating func latestPeek() -> Peek? {
            if let peek { return peek }
            peek = first.next().map(Peek.first) ?? second.next().map(Peek.second)
            return peek
        }
        
        mutating func next() -> First.Element? {
            switch latestPeek() {
            case .none:
                return nil
            case .first(let peekValue):
                guard let newValue = second.next() else {
                    peek = nil
                    return peekValue
                }
                guard areInIncreasingOrder(newValue, peekValue) else {
                    peek = .second(newValue)
                    return peekValue
                }
                return newValue
            case .second(let peekValue):
                guard let newValue = first.next() else {
                    peek = nil
                    return peekValue
                }
                guard areInIncreasingOrder(newValue, peekValue) else {
                    peek = .first(newValue)
                    return peekValue
                }
                return newValue
            }
        }
    }
    
    func makeIterator() -> Iterator {
        .init(
            first: first.makeIterator(),
            second: second.makeIterator(),
            areInIncreasingOrder: areInIncreasingOrder
        )
    }
    
    var underestimatedCount: Int {
        first.underestimatedCount + second.underestimatedCount
    }
}
extension Sequence {
    func mergingSorted<S: Sequence<Element>>(withSorted sequence: S, by areInIncreasingOrder: @escaping (Element, Element) -> Bool) -> MergeSortedSequence<Self, S> {
        .init(first: self, second: sequence, areInIncreasingOrder: areInIncreasingOrder)
    }
}
extension Sequence where Element: Comparable {
    func mergingSorted<S: Sequence<Element>>(withSorted sequence: S) -> MergeSortedSequence<Self, S> {
        mergingSorted(withSorted: sequence, by: { $0 < $1 })
    }
}