How'd I go implementing a `List#sortedWith` that takes a comparator which can be suspended? Suppose...

# coroutines

[bloodshura]

How'd I go implementing a List#sortedWith that takes a comparator which can be suspended?

Suppose I'd need something like this:

someList.sortedWith { o1, o2 -> suspendedComparison(o1, o2) }

Where suspendedComparison is a function which returns Int (satisfying Comparator) and is a suspend fun...

[bloodshura]

This, as is, won't work because sortedWith takes a Comparator as an argument, whose SAM is not suspendable. But then, what are the alternatives? Will I need to implement a sorting algorithm from scratch just to make it suspendable?

[mbonnin]

Most likely not the answer you expected but you can wrap your suspendedComparison in runBlocking {}

[bloodshura]

Yeah haha, I'm looking for something that would not block, since these suspended comparisons could take some time (even seconds)...

[mbonnin]

I'm not sure there's a way to "rewrite" a regular function into a suspendable one

[mbonnin]

Maybe with some IR-compiler-plugin magic ?

[mbonnin]

That sounds involved though...

[ephemient]

if performance isn't a major concern as you'll be waiting for your comparator anyway, rolling your own sort is easy enough:

suspend fun <T> List<T>.sortedWith(comparator: suspend (a: T, b: T) -> Int): List<T> {
    if (size <= 1) return this
    val first = first()
    val (left, right) = drop(1).partition { comparator(first, it) >= 0 }
    return left.sortedWith(comparator) + first + right.sortedWith(comparator)
}

[ephemient]

heck you could even parallelize it:

suspend fun <T> List<T>.sortedWith(scope: CoroutineScope, comparator: suspend (a: T, b: T) -> Int): List<T> {
    if (size <= 1) return this
    val first = first()
    val (left, right) = drop(1).partition { comparator(first, it) >= 0 }
    val sortedLeft = scope.async { left.sortedWith(this, comparator) }
    val sortedRight = scope.async { right.sortedWith(this, comparator) }
    return sortedLeft.await() + first + sortedRight.await()
}

[ephemient]

you're not going to be able to magically make the existing sort method suspending. it boils down to re-using platform's (e.g. Java, JS) standard library sort

[ephemient]

K/N does have its own sort implementation so you could copy that, but it's a bit fancier than the ⬆️ dumb quicksort above https://github.com/JetBrains/kotlin-native/blob/master/runtime/src/main/kotlin/kotlin/collections/ArraySorting.kt

[bloodshura]

Thank you very much!