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 Scala DSA implementation can be compared directly with the other languages.

Basic Implementation

basic.scala 
object Main {
	def main(args: Array[String]): Unit = {
		val arr = Array(5, 1, 4, 2, 8)
		for (i <- 1 until arr.length) {
			val key = arr(i)
			var j = i - 1
			while (j >= 0 && arr(j) > key) {
				arr(j + 1) = arr(j)
				j = j - 1
			}
			arr(j + 1) = key
		}
		println(arr.mkString("[", ", ", "]"))
	}
}

Complexity

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

Implementation notes

  • val arr = Array(5, 1, 4, 2, 8) fixes the Scala Array[Int] reference, but the array slots are still mutable.
  • The outer loop for (i <- 1 until arr.length) uses an exclusive range, so index 0 starts as the sorted prefix and indices 1 through 4 are inserted.
  • val key = arr(i) copies the current Int before shifts overwrite slots; var j = i - 1 tracks the scan position moving left.
  • The while condition j >= 0 && arr(j) > key checks the lower bound before reading arr(j), then compares Scala Int values directly.
  • Shifting is assignment, arr(j + 1) = arr(j), followed by j = j - 1; the final write-back is arr(j + 1) = key.
  • The trace shows [5, 1, 4, 2, 8], then inserting 1 gives [1, 5, 4, 2, 8], shifting 5 for key 4 gives [1, 4, 5, 2, 8], and shifting 5 and 4 for key 2 gives [1, 2, 4, 5, 8].
  • println(arr.mkString("[", ", ", "]")) prints the final 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.