Sorted and sortedBy in Kotlin - Time & Space Complexity

Time Complexity: Sorted and sortedBy

O(n log n)

Understanding Time Complexity

When we sort a list in Kotlin using sorted or sortedBy, the time it takes depends on how many items we have.

We want to know how the work grows as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val numbers = listOf(5, 3, 8, 1, 2)

// Sort numbers in ascending order
val sortedNumbers = numbers.sorted()

// Sort numbers by their negative value
val sortedByNegative = numbers.sortedBy { -it }

This code sorts a list of numbers in two ways: normal ascending order and by a custom rule.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing elements during sorting.
• How many times: The sorting algorithm compares elements multiple times, depending on the list size.

How Execution Grows With Input

As the list gets bigger, the number of comparisons grows faster than the list size itself.

Input Size (n)	Approx. Operations
10	About 30 to 40 comparisons
100	About 700 to 1000 comparisons
1000	About 10,000 to 15,000 comparisons

Pattern observation: The work grows roughly as n log n, so doubling the list size makes the work about twice as big.

Final Time Complexity

Time Complexity: O(n log n)

This means the sorting work grows a bit faster than the list size but much slower than if it grew with the square of the list size.

Common Mistake

[X] Wrong: "Sorting a list always takes the same time no matter how big it is."

[OK] Correct: Sorting takes more time as the list grows because more comparisons are needed.

Interview Connect

Understanding how sorting time grows helps you explain your choices clearly and shows you know how to handle bigger data smoothly.

Self-Check

"What if we used a list that is already sorted? How would the time complexity change when using sorted or sortedBy?"