---

theme: qklhk-chocolate highlight: xcode

Good morning, Kotlin enthusiasts. I'm sure you're all already experts at sorting—who hasn't spent months grinding LeetCode?

But I still hope you'll take five minutes to see how sorting is actually implemented in Kotlin. In this era, you might just end up optimizing a few lines of code for your AI partner, or even adding a note to your AGENTS.md file: if you need to sort, use the following methods.

Sorting

Sorting a collection in Kotlin doesn't seem complicated: ascending with sorted(), descending with sortedDescending(), and sorting by a field with sortedBy().

If you dig a little deeper, you'll find that "rearranging elements" actually encompasses at least three completely different things:

• Sorting: rearranging elements according to some rule;
• Reversing: flipping the current order of the collection;
• Shuffling: randomly rearranging the elements.

The results, complexity, and whether the original collection is modified all differ for these three operations. In particular, sortedDescending() and reversed(), while they can sometimes produce the same result, express completely different intentions.

This article starts with the most common APIs and gradually looks into the Kotlin standard library's implementation.

Sorting, Reversing, and Shuffling

Suppose we have the following collection:

val numbers = listOf(3, 1, 2)

Calling the three functions:

println(numbers.sorted())    // [1, 2, 3]
println(numbers.reversed())  // [2, 1, 3]
println(numbers.shuffled())  // result may vary each time

sorted() reorders elements based on their size; reversed() doesn't care about element size, it does only one thing—flip the original order; shuffled() generates a random permutation.

Therefore, if a collection is already sorted in ascending order:

val sorted = listOf(1, 2, 3)

println(sorted.sortedDescending()) // [3, 2, 1]
println(sorted.reversed())         // [3, 2, 1]

The two happen to produce the same result. But as soon as the original collection is not in ascending order, this equivalence disappears.

Natural Order Sorting

Kotlin provides two fundamental sorting functions:

• sorted(): sorts in ascending natural order;
• sortedDescending(): sorts in descending natural order.

For example:

val names = listOf("rock", "byte", "coding")

println(names.sorted())
// [byte, coding, rock]

println(names.sortedDescending())
// [rock, coding, byte]

The "natural order" here comes from the element's own Comparable implementation.

Common types like String and Int already implement Comparable, so you can call sorted() directly. For custom types, you can also define a default order by implementing Comparable:

data class Developer(
    val name: String,
    val experience: Int,
) : Comparable<Developer> {

    override fun compareTo(other: Developer): Int {
        return experience.compareTo(other.experience)
    }
}

Now, the natural order for Developer is ascending by years of experience:

val developers = listOf(
    Developer("compose", 5),
    Developer("kotlin", 3),
    Developer("android", 7),
)

println(developers.sorted())
// [Developer(name=kotlin, experience=3),
//  Developer(name=compose, experience=5),
//  Developer(name=android, experience=7)]

However, implementing Comparable means we are expressing that this type has a clear, stable, and sufficiently universal default order.

If a sorting rule only applies to a specific screen or business scenario, there's no need to modify the data type just for sorting. Using a Comparator is usually more appropriate in such cases, which will be covered in detail later.

One more thing to note: sorted() and sortedDescending() both return a new List and do not modify the original collection.

val source = mutableListOf(3, 1, 2)
val result = source.sorted()

println(source) // [3, 1, 2]
println(result) // [1, 2, 3]

If you want to directly modify a MutableList or array, you should use in-place sorting functions like sort() and sortDescending().

You can often guess the behavior of most Kotlin functions from their English naming: sorted() implies the returned result has been sorted, while sort() implies sorting the current structure.

What sorted() Does Internally

Below is the core implementation of Iterable<T>.sorted() in the Kotlin/JVM standard library. Some annotations have been omitted for readability:

public fun <T : Comparable<T>> Iterable<T>.sorted(): List<T> {
    if (this is Collection) {
        if (size <= 1) return this.toList()

        @Suppress("UNCHECKED_CAST")
        return (toTypedArray<Comparable<T>>() as Array<T>)
            .apply { sort() }
            .asList()
    }

    return toMutableList().apply { sort() }
}

It doesn't just use the same approach for all Iterables; it first checks if the current object is a Collection.

Collection: Convert to Array, Then Sort

Collection has a known size, so the standard library knows how much storage space is needed in advance. Therefore, when the number of elements is greater than 1, it follows this path:

Collection -> Array -> in-place sort -> List

This can be broken down into three steps:

1. Call toTypedArray() to copy the collection into a temporary array;
2. Call sort() on this temporary array to sort it in place;
3. Call asList() to wrap the sorted array into a List and return it.

asList() does not copy the array again; it returns a read-only List view backed by that array. Since this temporary array is not exposed to the caller, the return value can be treated as an independent sorted result from the outside.

When a collection has 0 or 1 elements, there's no need to sort at all, so it directly calls toList() and returns.

A result list is still created here, rather than simply returning this. This is because the return type of sorted() is a read-only List, and it should not leak the original mutable collection directly.

Regular Iterable: Collect into MutableList First

Iterable only guarantees access to an iterator; it doesn't guarantee knowing the number of elements in advance, nor that the underlying data supports random access.

Therefore, the standard library takes a different path:

return toMutableList().apply { sort() }

It first fully traverses the Iterable, collecting all elements into a new MutableList, and then sorts it in place.

Regardless of the path taken, sorting cannot look at only a portion of the data. To determine where an element should ultimately be placed, all participating elements must be gathered. Thus, sorting is fundamentally a stateful operation that requires holding all the data.

Sequence

In many cases, Sequence is quite special.

Sequence<T> does not inherit from Iterable<T>. It has its own set of sorted(), sortedBy(), and sortedWith() extension functions:

val sequence = sequenceOf(3, 1, 2)
val result: Sequence<Int> = sequence.sorted()

Sequence.sorted() still returns a Sequence, so from the API surface, it looks like a lazy intermediate operation. However, it is also a stateful operation: when iteration actually begins, it still needs to read all elements first, complete the sorting, and only then can it produce the first result.

This also means you should never call sorted() on an infinite sequence. Because it can never finish collecting all elements, it naturally can never produce the first sorted result.

This point is very, very important!!!

Quick Sort

sorted() does not always use dual-pivot quicksort. In fact, on the JVM, we need to distinguish between two types of arrays:

• Primitive type arrays like IntArray and LongArray, where the JDK often uses implementations like dual-pivot quicksort;
• Object arrays like Array<T>, where sorting must be stable, and common JDK implementations use stable sorting algorithms like TimSort.

Iterable<T>.sorted() converts to an object array, so it's closer to the second case.

Of course, the specific algorithm ultimately used by the standard library source code is a platform and JDK implementation detail and may change in the future. For business code, what's more reliable to depend on is the property explicitly promised by the API: these object sorting functions in Kotlin are stable sorts.

What is a Stable Sort

You probably know more about stable sorts than I do.

It roughly means: if two elements are considered equal by the comparator, they will maintain their original relative order after sorting.

For example:

data class Developer(
    val name: String,
    val experience: Int,
)

val developers = listOf(
    Developer("Alice", 5),
    Developer("Bob", 3),
    Developer("Charlie", 5),
)

val result = developers.sortedBy { it.experience }

The result is:

Bob(3), Alice(5), Charlie(5)

Alice and Charlie have the same years of experience, so their relative order after sorting remains unchanged.

This is especially important for multi-level sorting and staged sorting. However, in Kotlin, if the rules are clear, it's usually recommended to put multiple conditions into a single Comparator, which is easier to read.

Using sortedWith()

When objects have no natural order, or the current scenario requires a temporary set of rules, you can use sortedWith():

val sortedByMultiple = developers.sortedWith(
    compareByDescending<Developer> { it.experience }
        .thenBy { it.name }
)

This code expresses two sorting conditions:

1. First, sort by years of experience in descending order;
2. If years of experience are equal, sort by name in ascending order.

The output looks something like this:

Developer(name=android, experience=7)
Developer(name=compose, experience=5)
Developer(name=kotlin, experience=3)

compareBy(), compareByDescending(), thenBy(), and thenByDescending() are essentially helping us compose Comparators.

If written manually, it would look something like this:

val comparator = Comparator<Developer> { left, right ->
    val experienceResult =
        right.experience.compareTo(left.experience)

    if (experienceResult != 0) {
        experienceResult
    } else {
        left.name.compareTo(right.name)
    }
}

Clearly, using the comparator factories provided by the standard library is more concise and less prone to mixing up ascending and descending order.

The Source Code for sortedWith()

The implementation of sortedWith() is almost identical to sorted():

public fun <T> Iterable<T>.sortedWith(
    comparator: Comparator<in T>,
): List<T> {
    if (this is Collection) {
        if (size <= 1) return this.toList()

        @Suppress("UNCHECKED_CAST")
        return (toTypedArray<Any?>() as Array<T>)
            .apply { sortWith(comparator) }
            .asList()
    }

    return toMutableList().apply {
        sortWith(comparator)
    }
}

The only real change is that a Comparator is passed in during sorting.

For Collection, it still converts to an array first, then calls the array's sortWith(comparator); for a regular Iterable, it converts to a MutableList first, then calls the list's sortWith(comparator).

This is a very common design pattern in the Kotlin standard library: first provide a fully capable low-level function, then compose it through easier-to-use functions, rather than copying the same sorting logic many times over.

The code we write ourselves will also eventually form a set of core logic, from which various business functions derive, change, and evolve.

A Better sortedWith() — sortedBy

If you just want to sort by a specific field, using sortedWith() directly can be a bit verbose:

developers.sortedWith(
    compareBy { it.experience }
)

So Kotlin also provides sortedBy():

val sortedByExperience = developers.sortedBy {
    it.experience
}

Its source code is very simple:

public inline fun <T, R : Comparable<R>> Iterable<T>.sortedBy(
    crossinline selector: (T) -> R?,
): List<T> {
    return sortedWith(compareBy(selector))
}

sortedBy() doesn't handle sorting itself; it does only two things:

1. Creates a Comparator using compareBy(selector);
2. Passes this Comparator to sortedWith().

Therefore, sortedBy() automatically inherits the implementation and optimization paths of sortedWith().

sortedByDescending() follows the same idea:

public inline fun <T, R : Comparable<R>>
    Iterable<T>.sortedByDescending(
        crossinline selector: (T) -> R?,
    ): List<T> {
    return sortedWith(compareByDescending(selector))
}

As for sortedDescending(), it also doesn't re-implement a descending sort logic:

public fun <T : Comparable<T>>
    Iterable<T>.sortedDescending(): List<T> {
    return sortedWith(reverseOrder())
}

reverseOrder() generates a Comparator that is the reverse of the natural order, and sortedWith() completes the actual sorting.

Their relationship can be simply understood as:

sortedDescending() ─┐
sortedBy()          ├─> construct Comparator ─> sortedWith()
sortedByDescending()┘

The Selector in sortedBy() May Execute Many Times

sortedBy { it.experience } looks like it first transforms each element into experience and then sorts those values, but that's not what actually happens.

The comparator created by compareBy(selector) calls the selector once for each element every time two elements are compared. An element typically participates in multiple comparisons during a full sort, so the selector can be executed many times.

If the selector just reads a field, there's no need to worry:

developers.sortedBy { it.experience }

But if it involves a database query, file read, complex parsing, or expensive computation, it's not suitable to write it directly like this:

items.sortedBy { calculateExpensiveKey(it) }

A safer approach is to compute the sort key once first:

val result = items
    .map { item -> item to calculateExpensiveKey(item) }
    .sortedBy { (_, key) -> key }
    .map { (item, _) -> item }

This adds an intermediate data structure but avoids repeatedly computing the expensive key during sorting.

Whether this is worthwhile depends on the collection size and the cost of the selector—this relies on the developer's experience.

Handling nulls During Sorting

The selector in sortedBy() can return a nullable type:

data class User(
    val name: String,
    val score: Int?,
)

By default, compareBy { it.score } treats null as smaller than any non-null value, so null values will appear first in ascending order.

If business rules require null to be placed last, you can specify it explicitly:

val comparator = compareBy<User, Int?>(
    nullsLast(naturalOrder())
) { it.score }

val result = users.sortedWith(comparator)

Rather than relying on default behavior, explicitly stating the position of null is often easier to understand, especially when the comparison rules are complex.

Don't Use Subtraction Directly When Writing Comparators

Some code uses subtraction of two integers to implement a comparator:

// Not recommended
val comparator = Comparator<Developer> { a, b ->
    a.experience - b.experience
}

I'm sure many developers write it this way often.

For ordinary small numbers, it seems fine. But if two values are near the boundaries of Int, the subtraction can overflow, ultimately producing a wrong order.

You should use compareTo() or compareValues():

val comparator = Comparator<Developer> { a, b ->
    a.experience.compareTo(b.experience)
}

Beyond this, a correct comparator should also maintain consistent rules. For example, if a > b and b > c, then the result should also satisfy a > c. Otherwise, the sorting result may be unpredictable, and some platform implementations might even throw an exception directly.

reversed(): Reverses the Current Order

After talking about sorting, let's look at reversing.

val list = listOf("kotlin", "Android", "skydoves")
val reversedList = list.reversed()

println(reversedList)
// [skydoves, Android, kotlin]

reversed() does not compare any elements. It only cares about the current position of elements, swapping the first with the last, the second with the second-to-last, and so on, until it reaches the middle.

The core implementation of Iterable<T>.reversed() is as follows:

public fun <T> Iterable<T>.reversed(): List<T> {
    if (this is Collection && size <= 1) {
        return toList()
    }

    val list = toMutableList()
    list.reverse()
    return list
}

As you can see, the process is very straightforward:

1. First handle the case of 0 or 1 element;
2. Call toMutableList() to create a copy;
3. Call reverse() on the copy;
4. Return the reversed result.

So reversed() does not modify the original collection:

val source = mutableListOf(1, 2, 3)
val result = source.reversed()

println(source) // [1, 2, 3]
println(result) // [3, 2, 1]

If you want to directly modify a mutable list, use reverse():

val source = mutableListOf(1, 2, 3)
source.reverse()

println(source) // [3, 2, 1]

The function names differ by just one letter d, but the behavior is completely different:

Function	Returns	Modifies Receiver
reversed()	new List	No
reverse()	Unit	Yes

Collections.reverse() on the JVM

On the JVM platform, MutableList.reverse() ultimately uses java.util.Collections.reverse(). It doesn't blindly use index-based access; instead, it chooses different paths based on the list type.

Its core logic can be simplified to:

public static void reverse(List<?> list) {
    int size = list.size();

    if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
        for (int i = 0, mid = size >> 1, j = size - 1;
             i < mid;
             i++, j--) {
            swap(list, i, j);
        }
    } else {
        ListIterator front = list.listIterator();
        ListIterator back = list.listIterator(size);

        for (int i = 0, mid = size >> 1; i < mid; i++) {
            Object value = front.next();
            front.set(back.previous());
            back.set(value);
        }
    }
}

Lists Supporting Random Access

ArrayList implements RandomAccess, so reading and writing elements by index is constant time, making it most suitable for swapping with left and right pointers:

[A, B, C, D]
 ↑        ↑
 i        j

First swap A and D, then swap B and C. The whole process only needs to traverse half the elements, and the time complexity remains O(n).

Lists Not Supporting Random Access

LinkedList does not implement RandomAccess. If you repeatedly called get(i) and set(i), each index access could potentially re-traverse the list, easily degrading to O(n²).

So Collections.reverse() switches to using two ListIterators for larger lists: one moving forward from the start, the other moving backward from the end. This way, it still only needs a linear traversal.

This implementation selects the appropriate traversal method based on the data structure's access characteristics. This kind of specialization was also discussed in the previous article.

reversed() and reverse() for Arrays

Arrays also provide reversed():

public fun <T> Array<out T>.reversed(): List<T> {
    if (isEmpty()) return emptyList()

    val list = toMutableList()
    list.reverse()
    return list
}

Note that it returns a new List<T> and does not modify the original array.

Array's reverse(), on the other hand, directly modifies the array itself. Its core implementation is the classic two-pointer swap:

public fun <T> Array<T>.reverse() {
    val midPoint = (size / 2) - 1
    if (midPoint < 0) return

    var reverseIndex = lastIndex

    for (index in 0..midPoint) {
        val tmp = this[index]
        this[index] = this[reverseIndex]
        this[reverseIndex] = tmp
        reverseIndex--
    }
}

For arrays of odd length, the middle element doesn't need to move; for even-length arrays, exactly size / 2 swaps occur.

The time complexity of the entire operation is O(n), and if you ignore the temporary swap variable, the extra space used is O(1).

asReversed(): A Reverse View Without Copying Data

If the receiver is a List, Kotlin also provides an easily overlooked function: asReversed().

val source = mutableListOf(1, 2, 3)
val view = source.asReversed()

println(view) // [3, 2, 1]

source += 4
println(view) // [4, 3, 2, 1]

reversed() copies elements and generates an independent result; asReversed() returns a reverse view of the original list. It doesn't need to copy the entire dataset, but when the original list changes, the view changes along with it.

Therefore, neither is absolutely better:

• Use reversed() when you need an independent snapshot;
• Use asReversed() when you want to avoid copying and can accept the result being linked to the original list.

shuffled(): Randomly Shuffling Order

Finally, let's look at shuffling:

val frameworks = listOf("Compose", "Flutter", "React")

println(frameworks.shuffled())
// Output may vary each time

The implementation of shuffled() is somewhat similar to reversed(): first create a mutable copy, then perform the in-place operation on the copy.

public fun <T> Iterable<T>.shuffled(): List<T> =
    toMutableList().apply { shuffle() }

Therefore, it also does not modify the original collection.

If you already have a MutableList and want to shuffle it directly, you can call shuffle():

val frameworks = mutableListOf("Compose", "Flutter", "React")
frameworks.shuffle()

shuffle and shuffled, at this moment, are just like sort and sorted.

Fisher–Yates Shuffle Algorithm

Kotlin's shuffle implementation uses the modern Fisher–Yates algorithm. The idea is to iterate from the end to the beginning, each time randomly selecting an element from the not-yet-finalized positions and placing it at the current position.

The core code is as follows:

public fun <T> MutableList<T>.shuffle(random: Random) {
    for (i in lastIndex downTo 1) {
        val j = random.nextInt(i + 1)
        this[j] = this.set(i, this[j])
    }
}

Seeing the last line for the first time might seem a bit tricky:

this[j] = this.set(i, this[j])

set(i, value) writes the new value and also returns the original element at position i. So this single line of code actually completes a swap:

val oldValueAtI = this.set(i, this[j])
this[j] = oldValueAtI

To see the whole process clearly, suppose we have a list:

[A, B, C, D]

First loop, i = 3, randomly get j = 1 from 0..3, swap B and D:

[A, D, C, B]

Now the last position is finalized and won't be touched again.

Second loop, i = 2, randomly select a position from 0..2. Suppose it picks j = 2, then C swaps with itself, and the list remains unchanged:

[A, D, C, B]

Third loop, i = 1, randomly get j = 0 from 0..1, swap A and D:

[D, A, C, B]

After the loop ends, the element at index 0 is naturally determined as well.

For array-based lists, this process only requires one backward traversal, so the time complexity is O(n). In-place shuffling itself only needs constant extra space; however, shuffled() needs to copy out a new list first, so overall it requires O(n) space for the result.

On the JVM, the no-argument MutableList.shuffle() directly delegates to java.util.Collections.shuffle(). OpenJDK checks if the list supports random access: for lists like ArrayList that implement RandomAccess, it swaps elements directly by index; for non-random access lists exceeding a size threshold, like LinkedList, it first copies elements into an array to perform the shuffle, then writes them back via an iterator, thus avoiding the O(n²) performance problem caused by frequent index access.

shuffle() for Arrays

The shuffle logic for arrays is almost the same, just using a temporary variable for swapping elements:

public fun <T> Array<T>.shuffle(random: Random) {
    for (i in lastIndex downTo 1) {
        val j = random.nextInt(i + 1)

        val copy = this[i]
        this[i] = this[j]
        this[j] = copy
    }
}

Arrays themselves support constant-time index access, so each swap is O(1), and the overall algorithm remains O(n).

An important property of Fisher–Yates is: as long as the random number generator itself is unbiased, every possible permutation has an equal probability of appearing.

How to Get Repeatable Results in Tests

The default shuffled() can produce different results each time, which is fine in practice but makes unit tests unstable.

Kotlin allows passing a specified random number generator:

val result = frameworks.shuffled(Random(42))

With a fixed seed, you can get a repeatable random sequence on the same platform and implementation, which is more suitable for testing and reproducing issues.

However, kotlin.random.Random is not designed for security-sensitive scenarios like passwords or tokens. If the random result involves security, you should use a platform-provided cryptographically secure random number generator.

Which Function Should You Choose?

Finally, let's put these functions together:

Requirement	Returns New Result	In-place Modification
Ascending natural order	sorted()	sort()
Descending natural order	sortedDescending()	sortDescending()
Sort by field	sortedBy() / sortedByDescending()	sortBy() / sortByDescending()
Complex comparison rule	sortedWith()	sortWith()
Reverse current order	reversed()	reverse()
Get reverse view	asReversed()	—
Random shuffle	shuffled()	shuffle()

Their common complexities are as follows:

Operation	Time Complexity	Space for New Result	Stable
Sort	O(n log n)	O(n)	Yes
Reverse	O(n)	O(n)	No comparison involved
Shuffle	O(n)	O(n)	No comparison involved

The space complexity in the table is for functions that return new results, like sorted(), reversed(), and shuffled(). In-place versions don't need to create another full result, but the specific sorting algorithm might still use extra temporary space.

Some Thoughts

Kotlin provides collection operation functions like sorted, sortedBy, sortedWith, reversed, and shuffled, allowing flexible adjustment of the arrangement order of elements in a collection. They not only support custom comparators but can also combine multiple sorting conditions, enabling us to process data in a functional style with more concise and clear code.

Some might ask: now that AI writing code is so common, is it still necessary to spend time looking at the internal implementations of these standard libraries?

My answer is: it's still necessary. Most of the time, AI just gets the functionality running. It tends to give a working answer, but it won't proactively think for you about things like "this selector will be called many times, should I compute the sort key first?" or "this list doesn't support random access, will in-place shuffling degrade?". These details are precisely where engineering experience truly shines. An excellent engineer's sensitivity to performance and code smell often surpasses AI—not because they remember more APIs, but because they know what happens behind a line of code.

So, the point of reading source code isn't to memorize implementations, but to build a kind of judgment: knowing where the AI's solution is good enough, and where you need to give it another push yourself. This judgment is precisely the thing engineers should hold onto most in the AI era.