Kotlin · Android

Kotlin Sorting Under the Hood: Why Reading Source Code Still Beats AI Guesswork

By RockByte · Aug 11, 2026

Read original on juejin.cn ↗ Google Translate ↗ Alt translation

AI coding assistants produce working Kotlin that often ignores whether a list supports random access, recomputes expensive sort keys inside comparators, or calls terminal operations on infinite sequences. Knowing the internal dispatch paths lets an engineer spot the performance regression before it ships.

Summary

Kotlin's `sorted()`, `reversed()`, and `shuffled()` functions look interchangeable at a glance but rest on fundamentally different implementations. `sorted()` branches on whether the receiver is a `Collection` or a plain `Iterable`, converting to an array when size is known to avoid repeated allocations. `reversed()` and `shuffled()` similarly create mutable copies before operating in place, while `asReversed()` returns a zero-copy view that tracks changes to the original list.

On the JVM, these functions delegate to `java.util.Collections` routines that inspect whether a list implements `RandomAccess`. `ArrayList` gets direct index swaps; `LinkedList` gets iterator-based traversal to avoid quadratic degradation. The Fisher–Yates shuffle and TimSort-backed stable sort are both platform details that a developer relying solely on AI suggestions would never see.

A `sortedBy` selector can fire many more times than expected because `compareBy` calls it on every comparison, not once per element. Expensive key computation inside that lambda, integer subtraction in a `Comparator`, and calling `sorted()` on an infinite `Sequence` are all real-world mistakes that surface only when you understand what the standard library actually does.

Takeaways

— `sorted()` checks whether the receiver is a `Collection` and converts it to a typed array before sorting; a plain `Iterable` is first collected into a `MutableList`.

— `sortedBy` does not pre-compute keys — the selector lambda runs on every comparison, so expensive logic should be extracted into a separate `map` step first.

— `Sequence.sorted()` is a stateful, terminal-like operation that must consume the entire sequence before yielding any result; calling it on an infinite sequence hangs forever.

— Kotlin's object sorting is stable (typically TimSort on JVM), meaning equal elements preserve their original relative order.

— Subtracting two integers in a `Comparator` can overflow near `Int` boundaries; use `compareTo` or `compareValues` instead.

— `reversed()` copies the list and reverses the copy; `asReversed()` returns a live view that reflects mutations to the original list without copying.

— `Collections.reverse()` on JVM switches between index-based swapping for `RandomAccess` lists and iterator-based reversal for `LinkedList` to avoid O(n²) degradation.

— The Fisher–Yates shuffle runs in O(n) time and, given an unbiased random source, produces every permutation with equal probability.

— Passing a seeded `Random` instance to `shuffled()` makes random output repeatable for tests; `kotlin.random.Random` is not suitable for cryptographic use.

Conclusions

AI code generators optimize for correctness of output, not for the cost path — they will happily put a database call inside a `sortedBy` lambda because the API shape is legal.

The `sortedBy` selector trap is a perfect example of a leaky abstraction: the function reads like a map-then-sort but behaves like a sort-with-repeated-evaluation, and only reading the source makes that clear.

Kotlin's naming convention (`sorted` vs `sort`, `reversed` vs `reverse`, `shuffled` vs `shuffle`) encodes mutability in a single letter, but the real complexity is in the JVM delegation that inspects `RandomAccess` — a detail invisible from the Kotlin side.

The warning about infinite sequences and `sorted()` is not academic; lazy collection pipelines make it easy to accidentally attach a terminal-like sorting operation to an unbounded stream, and the failure mode is a silent hang rather than an exception.

Concepts & terms

Stable sort

A sorting algorithm that preserves the relative order of elements that compare as equal. Kotlin's object sorting on JVM is stable (typically TimSort), which matters for multi-pass sorting where later sorts should not undo earlier ordering.

RandomAccess interface

A marker interface in `java.util` that signals a `List` supports fast (constant-time) indexed access. `ArrayList` implements it; `LinkedList` does not. The JDK's `Collections.reverse()` and `shuffle()` branch on this to avoid O(n²) performance on linked structures.

Fisher–Yates shuffle

An O(n) algorithm that produces an unbiased random permutation by iterating from the last index down to the second, swapping the current element with a randomly chosen element from the remaining unshuffled prefix.

TimSort

A hybrid stable sorting algorithm derived from merge sort and insertion sort, used as the default for sorting objects in many JDK implementations. It performs well on partially ordered data, which is common in real-world collections.

Source: juejin.cn ↗ Google Translate ↗ Backup ↗