Sleep, Sort, Repeat: Testing Kotlin Coroutines with Virtual Time

How long do you think this test takes to run? @Test fun `sleep sort should sort a list...

How long do you think this test takes to run?

@Test
fun `sleep sort should sort a list correctly`() = runTest {
    val unsorted = (1..100_000).map { Random.nextInt(0, Int.MAX_VALUE) }

    val sorted = unsorted.sleepSort()

    assertEquals(unsorted.sorted(), sorted)
}

It sorts 100,000 random integers (up to Int.MAX_VALUE) using Sleep Sort — an algorithm where each element waits in its own coroutine for a number of seconds equal to its value, then emits itself. A single element of Int.MAX_VALUE would take about 68 years to sleep through.

The test passes in about a second. Not a trick — kotlinx-coroutines-test is doing something genuinely clever, and it's worth knowing about whether or not you ever sort anything by sleeping. Let me show you.

What is Sleep Sort?

Sleep Sort is the kind of algorithm you find on a wiki at 1am and immediately want to implement. Start a task per element, have each one sleep for a duration proportional to its value, then collect the emissions in order. Smaller values wake up first, larger values wake up later, so the output comes out sorted.

It's a terrible sorting algorithm — but a fun fit for Kotlin coroutines. Coroutines are cheap (launching 100,000 of them is fine), delay is suspending rather than blocking (a suspended coroutine occupies no thread), and kotlinx-coroutines-test can fast-forward through delays. That last part is what makes the test above possible.

The implementation

suspend fun List<Int>.sleepSort(): List<Int> = coroutineScope {
    val sorted = Channel<Int>(size)

    launch {
        map { i ->
            launch {
                delay(i.seconds)
                sorted.send(i)
            }
        }.joinAll()
        sorted.close()
    }

    sorted.consumeAsFlow().toList()
}

For each element we launch a coroutine that delays for that many seconds, then sends the value into a channel (buffered to size so sends never suspend). An outer launch waits for all of them to finish, then closes the channel. Meanwhile consumeAsFlow().toList() is already collecting — elements arrive in delay-order, which is sorted order.

A small note on the API: this is restricted to non-negative integers, but not for the reason you'd expect. delay returns immediately for non-positive durations rather than throwing, so negative inputs all race to the channel at once and produce silently wrong output. A defensive version would start with require(all { it >= 0 }). Worth knowing about — sometimes a tolerant standard library hides a bug rather than preventing one.

(The repo has more on the implementation — the role of the outer launch, and what coroutineScope does for free. Linked at the end.)

Running it for real

First, let's see the algorithm work in real time:

suspend fun main() {
    val unsorted = listOf(5, 1, 3, 2, 1, 2, 3, 4)
    val (sorted, duration) = measureTimedValue { unsorted.sleepSort() }
    println("It took $duration to sort $sorted")
}

measureTimedValue runs a block, returns its result, and tells you how long it took — pleasant for this kind of thing.

It took 5.040657167s to sort [1, 1, 2, 2, 3, 3, 4, 5]

Five seconds for a list of eight integers. The result is sorted, and the runtime is bounded by the largest element, because that's the last coroutine to wake up.

Now think about that test from the top of the post: 100,000 random integers, each potentially up to Int.MAX_VALUE. With that many uniformly random values you're virtually guaranteed at least one above two billion, and the largest element drives the runtime — so the test should take decades. It runs in a second. So what's going on?

Virtual time

The trick is that runTest, from kotlinx-coroutines-test, uses virtual time:

@Test
fun `sleep sort should sort a list correctly`() = runTest {
    val unsorted = (1..100_000).map { Random.nextInt(0, Int.MAX_VALUE) }

    val (defaultSortResult, defaultSortDuration) = measureTimedValue {
        unsorted.sorted()
    }
    val (sleepSortResult, sleepSortDuration) = measureTimedValue {
        unsorted.sleepSort()
    }

    assertEquals(defaultSortResult, sleepSortResult)
    println("Default sort duration: $defaultSortDuration")
    println("Sleep sort duration: $sleepSortDuration")
}

Same sleepSort, same 100k integers, same delay(i.seconds) calls inside — but inside runTest, those delays don't cost real time:

Default sort duration: 45.769750ms
Sleep sort duration: 1.191051583s

Stdlib's sorted() still wins by a comfortable margin (it should, it's a real sorting algorithm), but the interesting number is the second one. Sleep sort, an algorithm whose runtime is theoretically bounded by the largest input value in seconds, finishes in 1.2 seconds for 100,000 random integers. That second is real CPU spent shuttling 100,000 coroutines through the scheduler — none of it is simulated delay.

What runTest does is swap in a TestCoroutineScheduler (paired with StandardTestDispatcher) with a virtual clock. When a coroutine inside the block calls delay(i.seconds), the scheduler doesn't actually sleep — it parks the coroutine in a queue keyed by its virtual wake-up time, then runs whatever's ready right now. When nothing's ready, it advances the virtual clock to the next-soonest wake-up and resumes that coroutine. Repeat until everything's done.

The relative ordering of delays is preserved (a 1-second delay still finishes before a 2-second one), but neither costs you real time. It's a great fit for testing time-dependent coroutine code without sitting around watching the test run.

Wrapping up

Sleep sort is a joke. runTest and virtual time are not. The joke was a useful excuse to look at how kotlinx-coroutines-test lets you write tests for time-dependent coroutine code that finish in milliseconds instead of years.

The same technique applies anywhere time is the dependency: retry-with-backoff, polling, debounce, scheduled jobs — anywhere a test would otherwise have to wait for something to happen.

If you want to dig deeper — the implementation details, what happens at the edges (nanoseconds, milliseconds, scaling to millions), and the cases where virtual time will quietly lie to you — there's a "Going deeper" section in the repo's README that picks up where this article leaves off:

{% github tibtof/kotlin-sleep-sort %}

If you've hit a case where virtual time gave you false confidence — a test passing that failed in production — I'd genuinely like to hear about it in the comments.