Kotlin sorting and binary search

Sort lists with sorted and sortedBy, and find a value or its insertion point with binarySearch.

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]

Explanation

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.

Explore the dry run

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]

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.

Kotlin sorting and binary search

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading