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

sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.

Basic Implementation

basic.R
Replay: real traced execution (multi-file project)
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 = "")

  1. arr ← [5, 1, 4, 2, 8]

    1arr <- c(5, 1, 4, 2, 8)2for (i in 2:length(arr)) {
    values this step[5, 1, 4, 2, 8]arr

  2. arr ← [1, 5, 4, 2, 8]

    2for (i in 2:length(arr)) {3	key <- arr[i]4	j <- i - 1
    values this step[5, 1, 4, 2, 8] → [1, 5, 4, 2, 8]arr1key

  3. arr ← [1, 4, 5, 2, 8]

    4j <- i - 15while (j >= 1 && arr[j] > key) {6	arr[j + 1] <- arr[j]
    values this step[1, 5, 4, 2, 8] → [1, 4, 5, 2, 8]arr4key

  4. arr ← [1, 2, 4, 5, 8]

    4j <- i - 15while (j >= 1 && arr[j] > key) {6	arr[j + 1] <- arr[j]
    values this step[1, 4, 5, 2, 8] → [1, 2, 4, 5, 8]arr2key

  5. stdout ← [1, 2, 4, 5, 8]

    1arr <- c(5, 1, 4, 2, 8)2for (i in 2:length(arr)) {
    values this step[1, 2, 4, 5, 8]stdout[1, 2, 4, 5, 8]arr

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].