Bubble, Insertion, and Selection Sort

Compare simple sorts through their invariants

Insertion sort maintains a sorted prefix and inserts the next value into it. Bubble sort repeatedly exchanges adjacent inversions; selection sort chooses the next minimum and places it at the boundary. All have quadratic worst-case time in their basic forms.

Copy codefun insertionSort(values: IntArray) {
    for (i in 1 until values.size) {
        val value = values[i]
        var j = i - 1
        while (j >= 0 && values[j] > value) {
            values[j + 1] = values[j]
            j--
        }
        values[j + 1] = value
    }
}

The strict > comparison preserves equal elements' relative order. Already sorted input takes linear comparisons because no shifting is required. Basic selection sort still scans the remaining suffix and is generally unstable when it swaps the selected minimum.

Exercise

Trace [4, 2, 2, 1], labeling equal twos so stability is visible. Count comparisons and writes for sorted and reverse-sorted inputs.

Check: include empty and singleton arrays; confirm sorted output is also a permutation of the original, since returning an empty array would otherwise be trivially sorted.

Further reading: Elementary sorts