mergeSequences.swift

struct SortedMergeSequence<Element: Comparable> : Sequence, IteratorProtocol {
    var iterators: [AnyIterator<Element>]
    var lastElements: [Element?]

    mutating func next() -> Element? {
        var smallest: Element? = nil
        var smallestIndex : Int? = nil
        for index in lastElements.indices {
            guard let element = lastElements[index] else { continue }
            if (smallest == nil || element < smallest!) {
                smallest = element
                smallestIndex = index
            }
        }
        guard let index = smallestIndex else { return nil }
        lastElements[index] = iterators[index].next()
        return smallest
    }

    init(sequences: [AnySequence<Element>]) {
        iterators = sequences.map { $0.makeIterator() }
        lastElements = iterators.map { $0.next() }
    }

    init(arrays: [Array<Element>]) {
        self.init(sequences: arrays.map { AnySequence($0) })
    }
}

let a = SortedMergeSequence(arrays: [[1,3,5,7], [2,4,6,8], [0,9,10,11]])
for i in a {
    print(i)
}