Insertion Sort Algorithm in DSA Go

Mental Model

Insertion sort builds a sorted list one item at a time by inserting each new item into its correct place.

Analogy: Imagine sorting playing cards in your hand by picking one card at a time and placing it in the right position among the cards already held.

Unsorted array: [5, 3, 8, 6, 2]
Sorted part ↑          Unsorted part
[5] -> [3, 8, 6, 2]

Dry Run Walkthrough

Input: array: [5, 3, 8, 6, 2]

Goal: Sort the array in ascending order using insertion sort

Step 1: Take element 3 and compare with 5, shift 5 right and insert 3 before it

[3, 5, 8, 6, 2]

Why: 3 is smaller than 5, so it must be placed before 5 to keep sorted order

Step 2: Take element 8, it is greater than 5, so keep it in place

[3, 5, 8, 6, 2]

Why: 8 is already in correct position relative to sorted part

Step 3: Take element 6, compare with 8, shift 8 right, insert 6 before 8

[3, 5, 6, 8, 2]

Why: 6 is smaller than 8, so it must be inserted before 8

Step 4: Take element 2, compare with 8, shift 8 right; compare with 6, shift 6 right; compare with 5, shift 5 right; compare with 3, shift 3 right; insert 2 at start

[2, 3, 5, 6, 8]

Why: 2 is smallest, so it moves to the front by shifting all larger elements right

Result:

Sorted array: [2, 3, 5, 6, 8]

Annotated Code

DSA Go

package main

import "fmt"

func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i - 1
        // Move elements of arr[0..i-1], that are greater than key, to one position ahead
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j] // shift element right
            j--               // move left in sorted part
        }
        arr[j+1] = key // insert key at correct position
    }
}

func main() {
    arr := []int{5, 3, 8, 6, 2}
    insertionSort(arr)
    fmt.Println(arr)
}

for i := 1; i < len(arr); i++ {

iterate over each element starting from second to insert into sorted part

key := arr[i]

store current element to insert

j := i - 1

start comparing with previous sorted elements

for j >= 0 && arr[j] > key {

shift elements greater than key to the right

arr[j+1] = arr[j]

shift element right to make space

j--

move left in sorted part

arr[j+1] = key

insert key at correct sorted position

Output

[2 3 5 6 8]

Complexity Analysis

Time: O(n^2) because in worst case each insertion requires shifting all previous elements

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Compared to bubble sort, insertion sort is often faster on nearly sorted data because it minimizes swaps

Edge Cases

empty array

function returns immediately without changes

DSA Go

for i := 1; i < len(arr); i++ {

array with one element

no changes needed, array remains same

DSA Go

for i := 1; i < len(arr); i++ {

array already sorted

inner loop does not shift elements, minimal operations

DSA Go

for j >= 0 && arr[j] > key {

When to Use This Pattern

When you need to sort a small or nearly sorted list with simple code, reach for insertion sort because it inserts elements one by one in order.

Common Mistakes

Mistake: Not shifting elements before inserting key, causing overwriting
Fix: Shift elements greater than key to the right before placing key

Mistake: Starting outer loop from index 0 instead of 1
Fix: Start from index 1 because first element is trivially sorted

Summary

Insertion sort builds a sorted array by inserting each element into its correct place.

Use it for small or mostly sorted arrays where simple insertion is efficient.

The key insight is shifting larger elements right to make space for the current element.