Hey guys, Does anyone know a mechanism to sort a possibly infinite `Sequence` or one with a really a...

# getting-started

[asavio]

Hey guys,
Does anyone know a mechanism to sort a possibly infinite Sequence or one with a really a large count of objects lazily without it being too time consuming like the factory methods?

[Ruckus]

If you can find a way to sort an infinite number of things in finite time, you get all the money.

[asavio]

True, I guess I worded it wrong. Let say it’s not infinite. It’s just a sequence with a thousand objects. Is there a way to yield objects in a sorted order without waiting for all of the objects to arrive beforehand?

[ephemient]

unless you know something about the order they arrive in, you must receive every object to determine the minimum, which is the first element in the sorted result, so no.

[ephemient]

with additional knowledge - for example, if there is a guarantee that objects won't come out of order by more than some displacement of n - then you have some options

[asavio]

The use case is as follows.

There are five sequences, each of them in ascending order; they are then flattened into a single sequence, which is expected to be in a sorted order.

// list.size == 5

list.map {
    `yield objects in ascending order`()
}.asSequence().flatten()

Is there a solution for this?

[ephemient]

if they weren't flattened then there would be a solution

[asavio]

Could you elaborate?

[ephemient]

well-known CS algorithm,

fun <T : Comparable<T>> Iterable<Sequence<T>>.mergeSorted(): Sequence<T> = mergeSorted(comparator = naturalOrder())
fun <T> Iterable<Sequence<T>>.mergeSorted(comparator: Comparator<T>): Sequence<T> = sequence {
    val queue = PriorityQueue<Pair<Iterator<T>, T>>(compareBy(comparator) { it.second })
    mapNotNullTo(queue) { it.iterator().takeIf { it.hasNext() }?.let { it to it.next() } }
    while (queue.isNotEmpty()) {
        val (iterator, value) = queue.remove()
        yield(value)
        if (iterator.hasNext()) queue.add(iterator to iterator.next())
    }
}

fun main() {
    listOf(
        generateSequence(1) { 2 * it },
        generateSequence(1) { 3 * it },
        generateSequence(1) { 5 * it },
    ).mergeSorted().take(20).forEach { println(it) }
}

[asavio]

I see it! Thank you very much, @ephemient!