Data Structures, Algorithms and Programming Patterns · Part 6 of 9

Data Structures and Algorithms, Part 6: Sorting and Searching

Sorting and searching are the classic first algorithms for a reason: they are easy to state, there are many ways to solve them, and the costs differ enormously. In this part you will see why order is worth paying for, write binary search without the usual bugs, and meet the main sorting algorithms and when each one fits.

1. Why sorting and searching matter

Searching means finding an item in a collection. Sorting means putting the items in order, for example numbers from small to large or names from A to Z. These two jobs show up everywhere: a contacts app, a spreadsheet column, a file manager, a database index.

They are also the best place to learn how to think about algorithms. The problems are easy to state, there are many different solutions, and the costs differ by a lot. You get to see Big-O (Part 1) pay off in a very practical way.

That is the big idea of this part: pay once to put the data in order, then enjoy fast searches, easy duplicate detection, easy merging and easy range questions.

What sorting makes easy

• Searching drops from O(n) to O(log n) (binary search).
• Duplicates end up next to each other, so one pass finds them.
• Minimum, maximum, median and the k-th smallest are just positions in the list.
• Merging two sorted lists takes a single pass.
• Humans read ordered results far more easily.

Words we will use

• A comparison sort decides the order only by comparing two items at a time (is a smaller than b?). Bubble, insertion, merge and quicksort are all comparison sorts.
• A sort is stable if items that compare as equal keep their original relative order. If two students both have grade 90 and Ana came before Ben in the input, a stable sort keeps Ana before Ben.
• A sort is in-place if it rearranges the data inside the original array and needs only a small amount of extra memory, O(1) or O(log n).

2. Linear search: look at everything

The simplest search is to walk through the items from the start and compare each one with the target. If you find it, return its position. If you reach the end, return -1 (a common way to say “not found”).

It works on any list, sorted or not. In the worst case the target is last or missing, so you look at all n items: O(n) time, O(1) extra space.

fun linearSearch(list: List<Int>, target: Int): Int {
    for ((i, x) in list.withIndex()) {
        if (x == target) return i
    }
    return -1
}

fun linearSearchCounting(list: List<Int>, target: Int): Pair<Int, Int> {
    var looks = 0
    for ((i, x) in list.withIndex()) {
        looks++
        if (x == target) return i to looks
    }
    return -1 to looks
}

fun main() {
    val data = listOf(41, 7, 19, 3, 88, 25, 60)
    println(linearSearch(data, 88))     // 4
    println(linearSearch(data, 5))      // -1
    println(linearSearch(emptyList(), 5)) // -1

    val big = List(1000) { it * 3 }
    println("present at the end: " + linearSearchCounting(big, 2997))
    println("absent:             " + linearSearchCounting(big, 2998))
}

Linear search is perfectly fine for short lists or for data you will only search once. Sorting a list just to search it once would cost more than the search itself. The payoff comes when you search many times.

3. Binary search: halve the problem

Binary search finds a value in a sorted list by checking the middle item. If the middle is too small, the target must be in the right half. If it is too big, it must be in the left half. Either way you throw half the items away, then repeat on what is left.

It is the number guessing game: “I am thinking of a number from 1 to 100.” Guess 50. “Higher.” Guess 75. Seven guesses are always enough, because 27 = 128 is more than 100.

The cost: each step halves the range, so after k steps about n / 2k items remain. We stop when that reaches 1, which takes about log2 n steps. For one million items that is about 20 looks. For one billion, about 30. Time is O(log n) and extra space is O(1).

fun binarySearch(a: IntArray, target: Int): Int {
    var lo = 0
    var hi = a.size - 1
    while (lo <= hi) {
        val mid = lo + (hi - lo) / 2
        println("lo=$lo hi=$hi mid=$mid a[mid]=${a[mid]}")
        if (a[mid] == target) return mid
        if (a[mid] < target) lo = mid + 1 else hi = mid - 1
    }
    return -1
}

fun main() {
    val a = intArrayOf(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
    println("found at " + binarySearch(a, 23))
    println("---")
    println("found at " + binarySearch(a, 10))   // absent
    println("---")
    println("found at " + binarySearch(intArrayOf(), 10))  // empty
}

The three classic bugs

Binary search is famous for being easy to explain and surprisingly easy to get wrong. Almost every mistake is one of these three.

1. The middle overflows. The obvious (lo + hi) / 2 adds two numbers that might be near the top of the Int range. The sum wraps around to a negative number and you index outside the array. Use lo + (hi - lo) / 2, which never overflows.

fun main() {
    val lo = 2_000_000_000
    val hi = 2_100_000_000
    println("max Int      = ${Int.MAX_VALUE}")
    println("(lo + hi)/2  = ${(lo + hi) / 2}      <- wrapped around, negative!")
    println("lo+(hi-lo)/2 = ${lo + (hi - lo) / 2}  <- correct")
}

2. Off-by-one errors. You must decide what lo and hi mean and stick to it. In the version above both are inclusive (the answer can be at lo or at hi), so the loop runs while lo <= hi and we move to mid + 1 or mid - 1. Mixing styles, for example starting hi at size but looping while lo <= hi, reads one past the end.

3. The infinite loop. If you write lo = mid or hi = mid without the + 1 or - 1, the range may stop shrinking. With lo = 4, hi = 5 the middle is 4, and lo = mid leaves lo = 4 forever. Every step must make the range strictly smaller.

First position of a value: lower bound

What if the list has duplicates, like [1, 3, 3, 3, 7]? Plain binary search may land on any of the 3s. A more useful question is: where is the first position whose value is at least the target? This is called the lower bound. It is also exactly the place where the target would be inserted to keep the list sorted, and it works even when the target is absent.

It uses a different style: hi is exclusive (one past the last candidate), the loop runs while lo < hi, and we never stop early. We keep narrowing until lo == hi.

// First index whose value is >= target (a.size if there is none).
fun lowerBound(a: IntArray, target: Int): Int {
    var lo = 0
    var hi = a.size            // exclusive
    while (lo < hi) {
        val mid = lo + (hi - lo) / 2
        if (a[mid] < target) lo = mid + 1 else hi = mid
    }
    return lo
}

// How many times does target appear? Two lower bounds, no extra loop.
fun countOf(a: IntArray, target: Int): Int =
    lowerBound(a, target + 1) - lowerBound(a, target)

// Bonus: a sorted array rotated at some point, like [6, 7, 9, 1, 2, 4].
// At every step, at least one half is still sorted. Values are distinct.
fun searchRotated(a: IntArray, target: Int): Int {
    var lo = 0
    var hi = a.size - 1
    while (lo <= hi) {
        val mid = lo + (hi - lo) / 2
        if (a[mid] == target) return mid
        if (a[lo] <= a[mid]) {                       // left half is sorted
            if (target >= a[lo] && target < a[mid]) hi = mid - 1 else lo = mid + 1
        } else {                                     // right half is sorted
            if (target > a[mid] && target <= a[hi]) lo = mid + 1 else hi = mid - 1
        }
    }
    return -1
}

fun main() {
    val a = intArrayOf(1, 3, 3, 3, 7, 9)
    println("lowerBound(3) = ${lowerBound(a, 3)}")   // 1, the first 3
    println("lowerBound(4) = ${lowerBound(a, 4)}")   // 4, where 4 would go
    println("lowerBound(0) = ${lowerBound(a, 0)}")   // 0
    println("lowerBound(100) = ${lowerBound(a, 100)}") // 6, past the end
    println("count of 3 = ${countOf(a, 3)}, count of 5 = ${countOf(a, 5)}")

    val rotated = intArrayOf(6, 7, 9, 1, 2, 4)
    println("rotated: 2 is at ${searchRotated(rotated, 2)}, 9 is at ${searchRotated(rotated, 9)}, 5 is at ${searchRotated(rotated, 5)}")
}

Binary search works on more than lists. Any time you can ask a yes or no question that flips from “no” to “yes” exactly once as a number grows (“is a speed of x fast enough?”), you can binary search over the answer. You will see that trick again in Part 8.

4. Simple sorts: bubble, selection, insertion

Let us start with three easy sorts. All three take O(n²) time in the worst case, so you would not use them for a million items, but they are short, they are in-place, and they teach the core idea: put one more item in its correct place, then repeat.

Bubble sort

Walk through the list and swap any neighbours that are in the wrong order. After one pass the largest item has “bubbled” to the end. Repeat on the shorter remaining list. If a whole pass makes no swap, the list is already sorted and we stop early. Stable.

Selection sort

Find the smallest item in the unsorted part and swap it to the front of that part. Repeat. It always does about n²/2 comparisons, even on sorted input, but it makes at most n - 1 swaps, which matters if swapping is expensive. Not stable, because a long-distance swap can jump an item over its equal.

Insertion sort

Keep the left part of the array sorted. Take the next item (the key), shift every bigger item in the sorted part one step right, and drop the key into the gap. Stable and in-place.

fun swap(a: IntArray, i: Int, j: Int) {
    val t = a[i]; a[i] = a[j]; a[j] = t
}

fun bubbleSort(a: IntArray) {
    for (end in a.size - 1 downTo 1) {
        var swapped = false
        for (i in 0 until end) {
            if (a[i] > a[i + 1]) { swap(a, i, i + 1); swapped = true }
        }
        if (!swapped) return          // already sorted: stop early
    }
}

fun selectionSort(a: IntArray) {
    for (i in 0 until a.size - 1) {
        var smallest = i
        for (j in i + 1 until a.size) if (a[j] < a[smallest]) smallest = j
        swap(a, i, smallest)
    }
}

fun insertionSort(a: IntArray, trace: Boolean = false) {
    for (i in 1 until a.size) {
        val key = a[i]
        var j = i - 1
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j]           // shift the bigger item right
            j--
        }
        a[j + 1] = key                // drop the key into the gap
        if (trace) println("after inserting a[$i]=$key: ${a.toList()}")
    }
}

fun main() {
    val original = intArrayOf(5, 2, 4, 6, 1, 3)

    val b = original.copyOf(); bubbleSort(b); println("bubble:    ${b.toList()}")
    val s = original.copyOf(); selectionSort(s); println("selection: ${s.toList()}")
    println("insertion, step by step (start: ${original.toList()}):")
    val ins = original.copyOf(); insertionSort(ins, trace = true)
}

Insertion sort loves nearly sorted data

Look at the inner while loop of insertion sort: it only runs as long as items are out of order. On a list that is already sorted it never runs, so the whole sort is O(n). On a list where only a few items are out of place, it is close to O(n). On a reversed list it is the full O(n²). That is why serious libraries use insertion sort for small chunks, and for data that is “almost done”, such as a leaderboard with one new score.

// Returns how many times an item was shifted right.
fun insertionSortShifts(a: IntArray): Int {
    var shifts = 0
    for (i in 1 until a.size) {
        val key = a[i]
        var j = i - 1
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; shifts++ }
        a[j + 1] = key
    }
    return shifts
}

fun main() {
    val n = 1000
    val sorted = IntArray(n) { it }
    val nearly = IntArray(n) { it }.also {          // swap three neighbouring pairs
        for (i in intArrayOf(100, 500, 900)) { val t = it[i]; it[i] = it[i + 1]; it[i + 1] = t }
    }
    val reversed = IntArray(n) { n - it }

    println("already sorted:  ${insertionSortShifts(sorted)} shifts")
    println("nearly sorted:   ${insertionSortShifts(nearly)} shifts")
    println("reverse sorted:  ${insertionSortShifts(reversed)} shifts")
}

5. Merge sort: divide and conquer

The simple sorts are slow because each item may travel a long way one step at a time. Merge sort uses a different idea called divide and conquer: split the problem into smaller copies of itself, solve those, and combine the answers.

1. Divide: split the list into a left half and a right half.
2. Conquer: sort each half (by calling the same function; a list of 0 or 1 items is already sorted).
3. Combine: merge the two sorted halves into one sorted list.

The magic is the merge step. Two sorted lists can be combined with two fingers: point at the front of each list, take the smaller front item, move that finger forward, and repeat. Each item is touched once, so merging n items costs O(n).

The cost of the whole sort: the halving gives about log n levels, and each level does O(n) merging, so the total is O(n log n). This holds in the best, average and worst case. For a million items that is about 20 million steps instead of a trillion for O(n²).

Merge sort needs O(n) extra space for the merged lists. It is stable as long as the merge takes from the left list when two items are equal (the <= in the code below).

fun merge(left: List<Int>, right: List<Int>): List<Int> {
    val out = ArrayList<Int>(left.size + right.size)
    var i = 0
    var j = 0
    while (i < left.size && j < right.size) {
        // <= takes from the left on ties, which keeps the sort stable
        if (left[i] <= right[j]) out.add(left[i++]) else out.add(right[j++])
    }
    while (i < left.size) out.add(left[i++])     // leftovers from one side
    while (j < right.size) out.add(right[j++])
    return out
}

fun mergeSort(a: List<Int>): List<Int> {
    if (a.size <= 1) return a                    // base case: already sorted
    val mid = a.size / 2
    val left = mergeSort(a.subList(0, mid))
    val right = mergeSort(a.subList(mid, a.size))
    return merge(left, right)
}

fun main() {
    println(merge(listOf(1, 4, 9), listOf(2, 3, 10, 11)))
    println(mergeSort(listOf(5, 2, 9, 1, 7, 3, 8, 4)))
    println(mergeSort(listOf(3, 1, 3, 1, 3)))    // duplicates
    println(mergeSort(emptyList()))
    println(mergeSort(listOf(42)))
    println(mergeSort(List(10) { 10 - it }))     // reverse sorted
}

Merge sort is a great choice when you need guaranteed O(n log n), when stability matters, or when the data is too big for memory and sits on disk in pieces (merging sorted pieces is the heart of “external sorting”).

6. Quicksort: partition around a pivot

Quicksort also divides and conquers, but it does the hard work before the recursive calls instead of after. It picks one item, the pivot, and partitions the array: everything smaller than the pivot moves to its left, everything bigger moves to its right. The pivot is now in its final sorted position. Then it sorts the left part and the right part the same way.

Choosing the pivot

Quicksort is fast only if the pivot splits the array into two parts of similar size. Then there are about log n levels and each level does O(n) work: O(n log n) on average.

If the pivot is always the smallest or largest item, one side is empty and the other has n - 1 items. The recursion becomes n levels deep and the total is O(n²). This is the worst case. It happens if you always pick the first or last item and the input is already sorted. Common fixes: pick the middle item, pick a random item, or take the median of the first, middle and last.

Another trap is many equal items. The simple partition above treats equal items as “not smaller”, so a list of identical numbers splits badly. Production code uses a three-way partition (smaller, equal, larger) to avoid this. The demo below lets you see the damage.

Quicksort works in-place: it only swaps items inside the array. It needs O(log n) stack space for the recursion on average. It is not stable, since swaps jump over equal items. In practice it is often the fastest comparison sort, because it is cache-friendly and does little extra work.

var comparisons = 0

fun swap(a: IntArray, i: Int, j: Int) {
    val t = a[i]; a[i] = a[j]; a[j] = t
}

// Uses a[hi] as the pivot. Returns the pivot's final index.
fun partition(a: IntArray, lo: Int, hi: Int): Int {
    val pivot = a[hi]
    var i = lo
    for (j in lo until hi) {
        comparisons++
        if (a[j] < pivot) { swap(a, i, j); i++ }
    }
    swap(a, i, hi)
    return i
}

fun quickSort(a: IntArray, lo: Int = 0, hi: Int = a.size - 1) {
    if (lo >= hi) return
    swap(a, lo + (hi - lo) / 2, hi)   // use the middle item as the pivot
    val p = partition(a, lo, hi)
    quickSort(a, lo, p - 1)
    quickSort(a, p + 1, hi)
}

fun main() {
    // One partition step, matching the picture above
    val a = intArrayOf(7, 2, 9, 4, 3, 8, 1, 6)
    val p = partition(a, 0, a.size - 1)
    println("after partition: ${a.toList()}  pivot index = $p")

    println(intArrayOf(5, 2, 9, 1, 7, 3, 8, 4).also { quickSort(it) }.toList())
    println(intArrayOf().also { quickSort(it) }.toList())
    println(intArrayOf(3, 3, 3, 1, 2, 2).also { quickSort(it) }.toList())

    val n = 1000
    comparisons = 0
    quickSort(IntArray(n) { (it * 7919) % n })       // a scrambled permutation of 0..999
    println("scrambled input:    $comparisons comparisons")
    comparisons = 0
    quickSort(IntArray(n) { it })                    // already sorted, but the middle pivot copes
    println("sorted input:       $comparisons comparisons")
    comparisons = 0
    quickSort(IntArray(n) { 5 })                     // every item equal: the bad case
    println("all items equal:    $comparisons comparisons")
}

7. Heap sort and counting sort

Heap sort in a paragraph

In Part 4 you met the heap, a tree stored in an array where the smallest (or largest) item is always on top and can be removed in O(log n). Heap sort uses that directly: put every item into a heap, then remove the top over and over. Items come out in order. That is n insertions and n removals at O(log n) each, so O(n log n) in every case. The classic in-place version builds the heap inside the array itself, using O(1) extra space, but it is not stable and is usually slower than quicksort in practice. Its real value is the guarantee: no bad inputs.

import java.util.PriorityQueue

fun heapSort(a: List<Int>): List<Int> {
    val heap = PriorityQueue<Int>()      // smallest item on top
    for (x in a) heap.add(x)             // n inserts, O(log n) each
    val out = ArrayList<Int>(a.size)
    while (heap.isNotEmpty()) out.add(heap.poll())   // n removals, O(log n) each
    return out
}

fun main() {
    println(heapSort(listOf(9, 4, 7, 1, 8, 2, 2)))
    println(heapSort(emptyList()))
}

Counting sort: beating n log n by not comparing

If the values are small whole numbers in a known range, such as ages from 0 to 120 or exam scores from 0 to 100, you can sort without comparing items at all. Make an array of counters, one per possible value. Walk the input once and add one to counts[value]. Then walk the counters in order and write each value out as many times as it was counted.

The cost is O(n + k) time and O(n + k) space, where k is the size of the range. If k is small this is faster than any comparison sort. If k is huge (say, any 32-bit number), the counter array is too big and the idea stops being useful.

fun countingSort(a: IntArray, maxValue: Int): IntArray {
    val counts = IntArray(maxValue + 1)
    for (x in a) counts[x]++                       // tally each value
    val out = IntArray(a.size)
    var next = 0
    for (v in 0..maxValue) {
        repeat(counts[v]) { out[next++] = v }      // write v, counts[v] times
    }
    return out
}

// Bucket idea: group items by a small key first, then deal with each group.
// Here we bucket scores into grades, then print the groups in order.
fun main() {
    val ages = intArrayOf(31, 18, 22, 18, 64, 31, 5, 0, 22)
    println(countingSort(ages, 120).toList())
    println(countingSort(intArrayOf(), 10).toList())

    val scores = listOf(95, 67, 82, 74, 100, 58, 88, 79, 91)
    val buckets = Array(11) { ArrayList<Int>() }   // one bucket per ten points
    for (s in scores) buckets[s / 10].add(s)
    for (b in buckets.indices) {
        if (buckets[b].isNotEmpty()) println("${b * 10}s: ${buckets[b].sorted()}")
    }
}

8. What Kotlin gives you: sorted, sortedBy, sortedWith

In real programs you almost never write your own sort. Kotlin and Java already have a very good one. Knowing what it does lets you use it with confidence.

Under the hood, sorting a list of objects uses TimSort. TimSort is a hybrid: it finds runs of data that are already in order, uses insertion sort on small pieces and merge sort to combine them. It takes O(n log n) in the worst case, close to O(n) on nearly sorted data, uses up to O(n) extra space, and is stable. Sorting an array of primitives such as IntArray uses a tuned quicksort instead (dual-pivot), which is not stable, but for plain numbers stability cannot be seen because equal numbers look identical.

Comparators and multi-key sorting

A comparator is a rule that says which of two items comes first. Kotlin builds them from small pieces: compareBy for the first key, thenBy for each tie-breaker, and the Descending variants to flip a key. Because the sort is stable, you can also sort in several passes, but one comparator is clearer.

data class Person(val name: String, val age: Int, val city: String)

fun main() {
    val people = listOf(
        Person("Mika", 31, "Osaka"),
        Person("Ana", 25, "Tokyo"),
        Person("Ben", 31, "Tokyo"),
        Person("Chen", 25, "Osaka"),
        Person("Dara", 31, "Osaka"),
        Person("Eli", 25, "Tokyo"),
    )

    println("by age (stable, so ties keep input order):")
    people.sortedBy { it.age }.forEach { println("  $it") }

    val cmp = compareBy<Person> { it.city }
        .thenByDescending { it.age }
        .thenBy { it.name }
    println("by city, then oldest first, then name:")
    people.sortedWith(cmp).forEach { println("  $it") }

    // In-place sorting of a mutable list, and a reversed comparator
    val names = mutableListOf("pear", "fig", "banana", "kiwi")
    names.sortWith(compareBy<String> { it.length }.thenBy { it })
    println(names)
    names.sortWith(compareByDescending<String> { it.length })
    println(names)
}

9. Comparing the algorithms

Here is everything side by side. “Space” means extra memory beyond the input.

Which one should I use?

• Just need a sorted list in a program: call sorted() or sortedBy. Done.
• Tiny or nearly sorted data: insertion sort.
• Need stability and a guaranteed bound: merge sort.
• Need in-place and fast on average: quicksort with a good pivot.
• Need a guaranteed bound and no extra memory: heap sort.
• Small integer range: counting sort.

Why comparison sorts cannot beat n log n

Here is a simple argument. Suppose you have n distinct items. They could be in n! different orders (n choices for the first place, n - 1 for the second, and so on). A sorting algorithm must figure out which one it is.

Each comparison is a yes or no question, so it can at best cut the number of possible orders in half. To narrow n! possibilities down to one, you need at least log2(n!) questions. It turns out that log2(n!) grows like n log n. So no algorithm that works only by comparing two items at a time can be faster than O(n log n) in the worst case.

import kotlin.math.ceil
import kotlin.math.ln

// log2(n!) = log2(1) + log2(2) + ... + log2(n)
fun log2Factorial(n: Int): Double {
    var sum = 0.0
    for (k in 2..n) sum += ln(k.toDouble()) / ln(2.0)
    return sum
}

fun main() {
    println("n     min comparisons   n*log2(n)")
    for (n in listOf(3, 5, 10, 100, 1000, 100000)) {
        val minimum = ceil(log2Factorial(n)).toLong()
        val nlogn = (n * (ln(n.toDouble()) / ln(2.0))).toLong()
        println("%-6d %-17d %d".format(n, minimum, nlogn))
    }
}

Binary search on a sorted list versus a hash lookup

Part 2 showed that a hash set can answer “is this value here?” in O(1) on average, which is faster than binary search's O(log n). So why ever sort? Because a sorted array can answer questions a hash cannot:

• the nearest value, the next larger value, or where a new value belongs;
• how many values lie in a range;
• the items in order, with no extra work;
• it needs less memory (no table of buckets), and its layout is friendly to the CPU cache.

If you only ever ask “is it there?”, use a hash set. If you need order, use a sorted array or a tree (Part 4).

fun lowerBound(a: IntArray, target: Int): Int {
    var lo = 0
    var hi = a.size
    while (lo < hi) {
        val mid = lo + (hi - lo) / 2
        if (a[mid] < target) lo = mid + 1 else hi = mid
    }
    return lo
}

fun main() {
    val sorted = IntArray(500_000) { it * 2 }            // 0, 2, 4, ...
    val hash = sorted.toHashSet()

    // Both can answer "is it there?"
    println("hash has 1234:  ${1234 in hash}")
    println("hash has 1235:  ${1235 in hash}")
    println("sorted has 1234: ${lowerBound(sorted, 1234).let { it < sorted.size && sorted[it] == 1234 }}")

    // Only the sorted array can answer these cheaply
    val i = lowerBound(sorted, 1235)
    println("smallest value >= 1235: ${sorted[i]}")
    println("values in [100, 200): ${lowerBound(sorted, 200) - lowerBound(sorted, 100)}")

    // How many halvings does a search need for one million items?
    var n = 1_000_000
    var steps = 0
    while (n > 0) { n /= 2; steps++ }
    println("about $steps looks to search one million sorted items")
}

10. Practice

Five exercises. The first two train the careful, edge-case-heavy thinking that binary search demands. The next two have you build the two halves of merge sort and the simplest sort. The last one uses the standard library the way real programs do. Every test list includes the empty case, one item, and duplicates where they make sense.

fun binarySearch(a: IntArray, target: Int): Int {
    TODO("keep lo and hi, check the middle, discard half")
}

fun binarySearch(a: IntArray, target: Int): Int {
    var lo = 0
    var hi = a.size - 1
    while (lo <= hi) {
        val mid = lo + (hi - lo) / 2
        if (a[mid] == target) return mid
        if (a[mid] < target) lo = mid + 1 else hi = mid - 1
    }
    return -1
}

fun firstIndexOf(a: IntArray, target: Int): Int {
    TODO("find the lower bound, then check that it really holds the target")
}

fun firstIndexOf(a: IntArray, target: Int): Int {
    var lo = 0
    var hi = a.size
    while (lo < hi) {
        val mid = lo + (hi - lo) / 2
        if (a[mid] < target) lo = mid + 1 else hi = mid
    }
    return if (lo < a.size && a[lo] == target) lo else -1
}

fun insertionSort(a: IntArray) {
    TODO("take each item and slide it left into the sorted part")
}

fun insertionSort(a: IntArray) {
    for (i in 1 until a.size) {
        val key = a[i]
        var j = i - 1
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j]
            j--
        }
        a[j + 1] = key
    }
}

fun mergeSorted(left: List<Int>, right: List<Int>): List<Int> {
    TODO("compare the front of each list, take the smaller one")
}

fun mergeSorted(left: List<Int>, right: List<Int>): List<Int> {
    val out = ArrayList<Int>(left.size + right.size)
    var i = 0
    var j = 0
    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) out.add(left[i++]) else out.add(right[j++])
    }
    while (i < left.size) out.add(left[i++])
    while (j < right.size) out.add(right[j++])
    return out
}

data class Student(val name: String, val grade: Int)

fun rank(students: List<Student>): List<Student> {
    TODO("build a comparator with compareBy, thenBy and a descending key")
}

data class Student(val name: String, val grade: Int)

fun rank(students: List<Student>): List<Student> =
    students.sortedWith(compareByDescending<Student> { it.grade }.thenBy { it.name })

11. Takeaways

• Sorting is work you do once so that later searches, merges and range questions become cheap.
• Binary search is easy to explain and easy to get wrong: say what lo and hi mean, use lo + (hi - lo) / 2, and always shrink the range.
• Lower bound (first position with value at least the target) answers several questions with one loop.
• Insertion sort is the right tool for tiny or nearly sorted data; merge sort for stability and guarantees; quicksort for fast in-place work with a sensible pivot.
• Comparison sorts need at least about n log n comparisons, because n! orders need log(n!) yes or no answers.
• In everyday Kotlin, call the built-in stable sort and build comparators with compareBy and thenBy.
• Next up: recursion, backtracking, greedy choices and dynamic programming.