Объединение двух отсортированных потоков в один упорядоченный поток

Условие

Функция получает два входных канала, каждый из которых генерирует конечную монотонно неубывающую последовательность целых чисел. Необходимо создать и вернуть канал, объединяющий элементы обоих источников так, чтобы полученный поток также был монотонно неубывающим.

Ответ

Держите по одному текущему элементу каждого потока и отправляйте меньший. Обычный fan-in через select не подходит: он смешивает порядок источников без сравнения значений.

Пример с конечными закрывающимися входами; nil трактуется как пустой источник:

func mergeSorted(a, b <-chan int) <-chan int {
    out := make(chan int)
    go func() {
        defer close(out)
        read := func(ch <-chan int) (int, bool) {
            if ch == nil { return 0, false }
            value, ok := <-ch
            return value, ok
        }
        x, ax := read(a)
        y, by := read(b)
        for ax || by {
            if ax && (!by || x <= y) {
                out <- x
                x, ax = read(a)
            } else {
                out <- y
                y, by = read(b)
            }
        }
    }()
    return out
}

Время O(n+m), дополнительная память O(1). Медленный источник может задержать весь вывод: без его следующего элемента нельзя гарантировать сортировку. Получатель обязан дочитать выход; для ранней отмены добавьте context на все блокирующие операции.