Kotlin sorting and binary search

Before you start

Kotlin lists and lambdas.

Sort lists with sorted and sortedBy, and find a value or its insertion point with binarySearch.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

sorted() returns a new list in natural order, sortedDescending() the reverse, and sortedBy { key } sorts by a key function. These functions do not change the original list, and the sort is stable, so equal elements keep their order. For text, natural order compares the characters, so capital letters come before lowercase ones. Sorting by lowercase gives the order people expect.

binarySearch works on a sorted list. If the element is found it returns its index. If not, it returns -(insertion point) - 1, a negative number. From a negative result r, the insertion point is -r - 1, and inserting there keeps the list sorted. The list must be sorted by the same ordering used for the search.

Code example

Kotlin

fun main() {
    val numbers = listOf(5, 2, 9, 1, 5, 6)
    println(numbers.sorted())
    println(numbers.sortedDescending())

    val sorted = numbers.sorted()
    println(sorted.binarySearch(9))
    val missing = sorted.binarySearch(4)
    println("4 would be inserted at ${-missing - 1}")

    val words = listOf("pear", "apple", "Fig")
    println(words.sorted())
    println(words.sortedBy { it.lowercase() })

    val people = listOf("Ada" to 30, "Bo" to 25, "Cy" to 30, "Di" to 25)
    println(people.sortedBy { it.second }.map { it.first })
}

Output

[1, 2, 5, 5, 6, 9]
[9, 6, 5, 5, 2, 1]
5
4 would be inserted at 2
[Fig, apple, pear]
[apple, Fig, pear]
[Bo, Di, Ada, Cy]

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1fun main() {

2 val numbers = listOf(5, 2, 9, 1, 5, 6)

3 println(numbers.sorted())

4 println(numbers.sortedDescending())

6 val sorted = numbers.sorted()

7 println(sorted.binarySearch(9))

8 val missing = sorted.binarySearch(4)

9 println("4 would be inserted at ${-missing - 1}")

11 val words = listOf("pear", "apple", "Fig")

12 println(words.sorted())

13 println(words.sortedBy { it.lowercase() })

15 val people = listOf("Ada" to 30, "Bo" to 25, "Cy" to 30, "Di" to 25)

16 println(people.sortedBy { it.second }.map { it.first })

17}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
A new sorted list; numbers is unchanged.	`—`	[1, 2, 5, 5, 6, 9]
The reverse order.	`—`	[1, 2, 5, 5, 6, 9] [9, 6, 5, 5, 2, 1]
9 is found at index 5.	`—`	[1, 2, 5, 5, 6, 9] [9, 6, 5, 5, 2, 1] 5
4 is absent, so the result is negative: -(2) - 1 = -3.	`—`	[1, 2, 5, 5, 6, 9] [9, 6, 5, 5, 2, 1] 5
Decode the insertion point: -(-3) - 1 = 2.	`—`	[1, 2, 5, 5, 6, 9] [9, 6, 5, 5, 2, 1] 5 4 would be inserted at 2
Natural order puts the capital F first.	`—`	[1, 2, 5, 5, 6, 9] [9, 6, 5, 5, 2, 1] 5 4 would be inserted at 2 [Fig, apple, pear]
Sorting by the lowercase key ignores case.	`—`	[1, 2, 5, 5, 6, 9] [9, 6, 5, 5, 2, 1] 5 4 would be inserted at 2 [Fig, apple, pear] [apple, Fig, pear]
A stable sort by age: Bo and Di (25) keep their order, then Ada and Cy (30).	`—`	[1, 2, 5, 5, 6, 9] [9, 6, 5, 5, 2, 1] 5 4 would be inserted at 2 [Fig, apple, pear] [apple, Fig, pear] [Bo, Di, Ada, Cy]

Behind the scenes

How Kotlin processes this code

Kotlin commonly compiles to JVM bytecode, which the JVM executes.

Cost and common mistakes

Sorting is O(n log n); binarySearch is O(log n) on a list with fast random access.

binarySearch on an unsorted list gives meaningless results without any error.
sorted() creates a new list. To sort in place use a MutableList and call sort().
Natural string order is not alphabetical for mixed case, and it ignores language-specific rules.

Try it yourself

How do you sort people by age and then name?

Reveal answer and reasoning

people.sortedWith(compareBy({ it.second }, { it.first })), comparing age first and name second.