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.

Basic Implementation

basic.sh 
#!/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'

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.