Sorting

Insertion Sort

Build the sorted prefix one item at a time, shifting larger values right until the current key can be inserted.

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this Kotlin DSA implementation can be compared directly with the other languages.

Basic Implementation

basic.kt 
fun main() {
	val arr = intArrayOf(5, 1, 4, 2, 8)
	for (i in 1 until arr.size) {
		val key = arr[i]
		var j = i - 1
		while (j >= 0 && arr[j] > key) {
			arr[j + 1] = arr[j]
			j--
		}
		arr[j + 1] = key
	}
	println(arr.joinToString(prefix = "[", postfix = "]"))
}

Complexity

  • Time: O(n^2) worst and average, O(n) best
  • Space: O(1)
  • Stable: yes

Implementation notes

  • Kotlin stores the input in a primitive IntArray from intArrayOf(5, 1, 4, 2, 8). The arr binding is a val, but the array slots are still mutated in place.
  • The outer loop uses for (i in 1 until arr.size), so each pass reads a non-null Int key from arr[i] without revisiting index 0.
  • key is a val copy of the current element, while j is a mutable var initialized to i - 1 and decremented during shifts.
  • The while guard j >= 0 && arr[j] > key short-circuits before arr[j] is read with a negative index, and uses strict Int comparison for stability.
  • Shifts are explicit slot writes: arr[j + 1] = arr[j], followed by the final placement arr[j + 1] = key; no new array is allocated for the sort.
  • The trace records [5, 1, 4, 2, 8], then [1, 5, 4, 2, 8], [1, 4, 5, 2, 8], and [1, 2, 4, 5, 8] after inserting 2.
  • println(arr.joinToString(prefix = "[", postfix = "]")) formats the mutated array as [1, 2, 4, 5, 8].
sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.