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

  • 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].
sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.