Bash Script for Insertion Sort with Example and Explanation

Use a Bash script with nested loops where the inner loop shifts elements right to insert the current element in sorted order, like: for ((i=1; i=0 && arr[j]>key)); do arr[j+1]=${arr[j]}; ((j--)); done; arr[j+1]=$key; done.

Examples

Input3 1 4 1 5

OutputSorted array: 1 1 3 4 5

Input10 9 8 7 6

OutputSorted array: 6 7 8 9 10

Input5

OutputSorted array: 5

How to Think About It

Think of sorting like organizing playing cards in your hand. You pick one card at a time and insert it into the correct position among the cards already sorted. In Bash, you compare each element with those before it and shift larger elements right to make space for the current element.

Algorithm

1

Start from the second element of the array.

2

Compare the current element with elements before it.

3

Shift all larger elements one position to the right.

4

Insert the current element into the correct position.

5

Repeat until the entire array is sorted.

Code

bash

#!/bin/bash
arr=(3 1 4 1 5)
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--))
  done
  arr[j+1]=$key
done

echo "Sorted array: ${arr[*]}"

Output

Sorted array: 1 1 3 4 5

Dry Run

Let's trace sorting the array [3, 1, 4, 1, 5] through the code

1

Start with i=1, key=1

Compare key=1 with arr[0]=3, shift 3 right, insert 1 at position 0

2

i=2, key=4

4 is greater than arr[1]=3, no shift, insert 4 at position 2

3

i=3, key=1

Compare with 4 and 3, shift both right, insert 1 at position 1

Iteration	Array State
Start	3 1 4 1 5
i=1	1 3 4 1 5
i=2	1 3 4 1 5
i=3	1 1 3 4 5

Why This Works

Step 1: Choosing the key element

We pick the element at index i as the key to insert it into the sorted part of the array.

Step 2: Shifting elements

Elements larger than the key are moved one position right to make space for the key.

Step 3: Inserting the key

The key is placed in the correct position where all elements before it are smaller or equal.

Alternative Approaches

Using a function to sort any input array

bash

#!/bin/bash
insertion_sort() {
  local -n arr=$1
  local n=${#arr[@]}
  for ((i=1; i<n; i++)); do
    local key=${arr[i]}
    local j=$((i-1))
    while ((j>=0 && arr[j]>key)); do
      arr[j+1]=${arr[j]}
      ((j--))
    done
    arr[j+1]=$key
  done
}

arr=(9 7 5 3 1)
insertion_sort arr
echo "Sorted array: ${arr[*]}"

This approach uses a Bash function and nameref for reusability but requires Bash 4.3+.

Sorting using external command 'sort'

bash

#!/bin/bash
arr=(3 1 4 1 5)
sorted=($(printf "%s\n" "${arr[@]}" | sort -n))
echo "Sorted array: ${sorted[*]}"

This is simpler and faster for large arrays but uses an external command instead of pure Bash logic.

Complexity: O(n^2) time, O(1) space

Time Complexity

Insertion sort uses nested loops: the outer loop runs n times, and the inner loop can run up to n times in worst case, resulting in O(n^2).

Space Complexity

It sorts the array in place, so it uses only constant extra space O(1).

Which Approach is Fastest?

Using the external 'sort' command is fastest for large data, but pure Bash insertion sort is good for learning and small arrays.

Approach	Time	Space	Best For
Insertion Sort in Bash	O(n^2)	O(1)	Small arrays, learning
Function with nameref	O(n^2)	O(1)	Reusable code, Bash 4.3+
External 'sort' command	O(n log n)	O(n)	Large arrays, performance