Sorting in Kotlin

In order to sort an array we can use the sort() function, which sorts its elements in ascending order. For descending order there is sortDescending(), and for a user-defined order there is sortWith().

Similarly, if we want to sort a mutable list, we can use sort(), which works the same way.

Important: Sorting in reverse or with a specified order using a comparator is possible only if we use objects and not primitives. This means that it will work for Array<Int> array, but not on IntArray, at least not as easy as we think.

Syntax:

Let's see some examples below. Sorting an array of integers in ascending order

val numbers = intArrayOf(11, 3, 7, 5, 2)

numbers.sort() // numbers becomes [2, 3, 5, 7, 11]

Sorting a mutable list of Ints in descending order

val arr = mutableListOf(11, 3, 7, 5, 2)

arr.sortDescending() // arr becomes [11, 7, 5, 3, 2]

Sorting an array of integers in descending order

val numbers = intArrayOf(11, 3, 7, 5, 2)

numbers.sortWith(Comparator.reverseOrder()) // compile error: unresolved reference 'sortWith'

Notice that we have an IntArray, so we won't be able to sort it in reverse directly! We need to transform it into an Array<Int> as below:

val numbers = intArrayOf(11, 3, 7, 5, 2)

// transform it to Array<Int>
val arr = numbers.toTypedArray()

// Now we can sort it
arr.sortWith(Comparator.reverseOrder()) //arr becomes [11, 7, 5, 3, 2]

Sorting an array of Strings in descending order

val names = arrayOf("Mircea", "Andy", "Xavier", "Michael", "Christina")

names.sortWith(Comparator.reverseOrder()) // names becomes [Xavier, Mircea, Michael, Christina, Andy]

Sort with custom function (comparator):

The sortWith() function supports a basic comparison function that we can use to specify how we want to sort:

fun compare(a: Int, b: Int): Int {
    return a - b
}

This can be written as a lambda function (nameless function we can easily pass to sortWith()) as follows:

{ a, b ->
    a - b
}

If the function just returns one thing, we can write it as follows:

{ a, b -> a - b }

When the sortWith() function compares two values, it sends the values to the compare function, and sorts the values according to the returned (negative, zero, positive) value:

• If the result is negative a is sorted before b.
• If the result is positive b is sorted before a.
• If the result is 0 no changes are done with the sort order of the two values.

All we need to is using the compare function (as a lambda function) inside the sortWith() function:

val numbers = arrayOf(3, 23, 12)

// using the short version of the lambda function
numbers.sortWith { a, b -> a - b } // numbers becomes [3, 12, 23]

To demonstrate a basic example, let’s assume the requirement for ordering a specific list is the length of the strings in the list, shortest to longest. We will be using the length property of each string to compare them.

val words = arrayOf("banana", "pie", "Washington", "book")

words.sortWith { a, b -> a.length - b.length } // words becomes [pie, book, banana, Washington]

Example: sorting array of pairs

Let's say we want to sort an array, where each element is another array consisting of two numbers.

This time we will be using Array<IntArray> since each IntArray element is treated as an object so it can be sorted with a compare function

val pairs = arrayOf(
    intArrayOf(1, 5),
    intArrayOf(12, 5),
    intArrayOf(10, 1),
    intArrayOf(1, 3)
)

pairs.sortWith { a, b ->
    // in case the first values of each pair are equal,
    // compare them using their second values
    if (a[0] == b[0]) {
        a[1] - b[1]
    } else {
        a[0] - b[0]
    }
}
// pairs becomes [[1, 3], [1, 5], [10, 1], [12, 5]]

Time Complexity:

Sorting an array via sort() or sortWith() takes O(n * log n * C) time, where C is the time taken to compare two elements from the array.

It takes O(1) (constant time) to compare two numbers, therefore sorting an array of numbers takes O(n log n).

However, it takes O(L) to compare two strings, therefore sorting an array of strings takes O(n * log n * L), where L is the average length of the strings.

Space Complexity:

The sort() function sorts the elements of an array in place (transforms the array directly, using no auxiliary data structure), so the extra space used for this is O(1).

Assignment
Follow the Coding Tutorial and let's sort some arrays.

Hint
Look at the examples above if you get stuck.