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

Basic Implementation

basic.R

arr <- c(5, 1, 4, 2, 8)
for (i in 2:length(arr)) {
	key <- arr[i]
	j <- i - 1
	while (j >= 1 && arr[j] > key) {
		arr[j + 1] <- arr[j]
		j <- j - 1
	}
	arr[j + 1] <- key
}
cat("[", paste(arr, collapse = ", "), "]
", sep = "")

Complexity

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

Implementation notes

Keep the explicit algorithmic steps instead of calling a standard-library sort. The replay is meant to expose comparisons, movement, and recursion.
The implementation is intentionally compact for learning and replay, not a production sorting utility.

sorted prefix Positions before the scan index are already sorted.

shifting Larger values move one slot right to make room for the key.