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 Bash 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.sh
Replay: real traced execution (multi-file project)
#!/usr/bin/env bash
set -euo pipefail
arr=(5 1 4 2 8)
n=${#arr[@]}
for ((i = 1; i < n; i++)); do
	key=${arr[i]}
	j=$((i - 1))
	while ((j >= 0 && arr[j] > key)); do
		arr[j+1]=${arr[j]}
		j=$((j - 1))
	done
	arr[j+1]=$key
done
printf '['
sep=''
for v in "${arr[@]}"; do
	printf '%s%d' "$sep" "$v"
	sep=', '
done
printf ']\n'

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

    1#!/usr/bin/env bash2set -euo pipefail
    values this step[5, 1, 4, 2, 8]arr

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

    5for ((i = 1; i < n; i++)); do6	key=${arr[i]}7	j=$((i - 1))
    values this step[5, 1, 4, 2, 8] → [1, 5, 4, 2, 8]arr1key

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

    7j=$((i - 1))8while ((j >= 0 && arr[j] > key)); do9	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]

    7j=$((i - 1))8while ((j >= 0 && arr[j] > key)); do9	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]

    13done14printf '['15sep=''
    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=(5 1 4 2 8) is the pinned Bash indexed array, and n=${#arr[@]} stores its length as 5.
  • for ((i = 1; i < n; i++)); do scans the unsorted suffix by index.
  • key=${arr[i]} saves the value being inserted before any shifting starts.
  • j=$((i - 1)) starts at the last index of the sorted prefix.
  • while ((j >= 0 && arr[j] > key)); do uses Bash arithmetic evaluation and keeps shifting while the value on the left is larger than key.
  • arr[j+1]=${arr[j]} shifts one slot right, then j=$((j - 1)) moves left.
  • After the loop, arr[j+1]=$key writes the saved key into its insertion slot.

Replay steps

start:      [5, 1, 4, 2, 8]
insert 1:   [1, 5, 4, 2, 8]
insert 4:   [1, 4, 5, 2, 8]
insert 2:   [1, 2, 4, 5, 8]
insert 8:   [1, 2, 4, 5, 8]
  • Output is built with printf '[', sep='', then for v in "${arr[@]}" and printf '%s%d' "$sep" "$v".
  • After each printed value, sep=', ' prepares the next separator, and printf ']\n' closes the line as [1, 2, 4, 5, 8].