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?"

Practice

1. What does the sorted() function do in Kotlin?

easy

A. It sorts the original list in place and returns nothing.

B. It arranges elements randomly in a new list.

C. It returns a new list with elements arranged in natural ascending order.

D. It filters elements based on a condition.

Solution

1. Step 1: Understand the purpose of sorted()

   The sorted() function creates a new list where elements are arranged in natural ascending order (numbers from smallest to largest, strings alphabetically).

2. Step 2: Check if original list changes

   The original list remains unchanged because sorted() returns a new sorted list without modifying the original.

3. Final Answer:

   It returns a new list with elements arranged in natural ascending order. -> Option C

4. Quick Check:

   sorted() = new ascending list [OK]

Hint: sorted() always returns a new ascending list [OK]

Common Mistakes:

• Thinking sorted() changes the original list
• Confusing sorted() with filtering
• Assuming sorted() arranges elements randomly

2. Which of the following is the correct syntax to sort a list of strings by their length using sortedBy in Kotlin?

easy

A. list.sortedBy { it.length }

B. list.sortedBy.length()

C. list.sortedBy(it.length)

D. list.sortedBy { length(it) }

Solution

1. Step 1: Identify correct lambda syntax for sortedBy

   The sortedBy function takes a lambda expression that returns the property to sort by. The correct syntax is list.sortedBy { it.property }.

2. Step 2: Check each option

   list.sortedBy { it.length } uses { it.length } which correctly accesses the length property of each string. Other options have syntax errors or incorrect usage.

3. Final Answer:

   list.sortedBy { it.length } -> Option A

4. Quick Check:

   sortedBy uses lambda with it.property [OK]

Hint: Use curly braces and 'it' to access property in sortedBy [OK]

Common Mistakes:

• Using parentheses instead of curly braces
• Calling length() as a function incorrectly
• Passing property outside lambda

3. What is the output of the following Kotlin code?

val numbers = listOf(5, 3, 8, 1)
val sortedNumbers = numbers.sortedBy { it % 3 }
println(sortedNumbers)

medium

A. [1, 3, 5, 8]

B. [3, 6, 9, 12]

C. [1, 5, 3, 8]

D. [3, 1, 5, 8]

Solution

1. Step 1: Calculate the sorting key for each element

   Calculate it % 3 for each number: 5 % 3 = 2, 3 % 3 = 0, 8 % 3 = 2, 1 % 3 = 1.

2. Step 2: Sort numbers by these keys

   Sort by keys in ascending order: 0 (3), 1 (1), 2 (5), 2 (8). So sorted list is [3, 1, 5, 8].

3. Final Answer:

   [3, 1, 5, 8] -> Option D

4. Quick Check:

   sortedBy { it % 3 } = [3, 1, 5, 8] [OK]

Hint: Calculate sorting key for each element before sorting [OK]

Common Mistakes:

• Sorting by values instead of keys
• Confusing modulo results
• Assuming sortedBy sorts original list

4. Identify the error in this Kotlin code snippet:

val fruits = listOf("apple", "banana", "cherry")
val sortedFruits = fruits.sortedBy(it.length)
println(sortedFruits)

medium

A. sortedBy cannot be used on lists of strings.

B. Missing curly braces around the lambda expression in sortedBy.

C. The list should be mutable to use sortedBy.

D. The println statement is incorrect.

Solution

1. Step 1: Check syntax of sortedBy usage

   The sortedBy function requires a lambda expression inside curly braces, like { it.length }. The code uses parentheses without braces, which is incorrect.

2. Step 2: Verify other options

   sortedBy works on lists of strings, the list can be immutable, and println is correct. So only the lambda syntax is wrong.

3. Final Answer:

   Missing curly braces around the lambda expression in sortedBy. -> Option B

4. Quick Check:

   sortedBy needs { } for lambda [OK]

Hint: Always use curly braces for lambda in sortedBy [OK]

Common Mistakes:

• Using parentheses instead of curly braces for lambda
• Thinking sortedBy needs mutable list
• Misunderstanding println usage

5. Given a list of data class objects data class Person(val name: String, val age: Int), how would you sort the list first by age ascending, then by name alphabetically using Kotlin's sorting functions?

hard

A. persons.sortedWith(compareBy({ it.age }, { it.name }))

B. persons.sortedBy { it.age + it.name }

C. persons.sortedBy { it.name }.sortedBy { it.age }

D. persons.sortedByDescending { it.age }.sortedBy { it.name }

Solution

1. Step 1: Understand multi-level sorting in Kotlin

   To sort by multiple properties, use sortedWith(compareBy(...)) passing lambdas for each property in priority order.

2. Step 2: Analyze options

   persons.sortedWith(compareBy({ it.age }, { it.name })) correctly uses compareBy with age first, then name. persons.sortedBy { it.age + it.name } incorrectly adds age and name (different types). persons.sortedBy { it.name }.sortedBy { it.age } sorts twice but second sort overrides first. persons.sortedByDescending { it.age }.sortedBy { it.name } sorts age descending, not ascending.

3. Final Answer:

   persons.sortedWith(compareBy({ it.age }, { it.name })) -> Option A

4. Quick Check:

   Use sortedWith(compareBy(...)) for multi-level sort [OK]

Hint: Use sortedWith(compareBy(...)) for sorting by multiple keys [OK]

Common Mistakes:

• Adding different types in sortedBy
• Chaining sortedBy loses previous sort
• Using sortedByDescending when ascending needed