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

arr <- c(5, 1, 4, 2, 8) creates the pinned numeric R vector.
R vectors are 1-based, so the outer loop starts at slot 2 with for (i in 2:length(arr)).
Each pass saves the current value in key <- arr[i] before shifting anything.
j <- i - 1 starts at the previous slot in the already-scanned prefix.
The while guard is j >= 1 && arr[j] > key, so the code checks the left boundary before reading arr[j].
Shifting is an in-place vector assignment: arr[j + 1] <- arr[j].
After each shift, j <- j - 1 moves left.
When shifting stops, arr[j + 1] <- key writes the saved value into the open slot.

Replay steps

start:        [5, 1, 4, 2, 8]
i=2, key=1:  [1, 5, 4, 2, 8]
i=3, key=4:  [1, 4, 5, 2, 8]
i=4, key=2:  [1, 2, 4, 5, 8]
i=5, key=8:  [1, 2, 4, 5, 8]

The final cat call combines "[", paste(arr, collapse = ", "), and a closing bracket string that contains the newline, so it prints [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.