Go Program for Insertion Sort with Example and Explanation

An insertion sort in Go can be done by looping through the array and inserting each element into its correct position using for loops and shifting elements; for example: for i := 1; i < len(arr); i++ { key := arr[i]; j := i - 1; for j >= 0 && arr[j] > key { arr[j+1] = arr[j]; j-- } arr[j+1] = key }.

Examples

Input[5, 2, 9, 1]

Output[1 2 5 9]

Input[3, 3, 2, 1]

Output[1 2 3 3]

Input[]

Output[]

How to Think About It

To sort an array using insertion sort, start from the second element and compare it with elements before it. Move the larger elements one position ahead to make space and insert the current element in the correct place. Repeat this for all elements until the array is sorted.

Algorithm

1

Start from the second element of the array.

2

Compare the current element with the elements before it.

3

Shift all elements that are greater than the current element one position to the right.

4

Insert the current element into the correct position.

5

Repeat steps 2-4 for all elements in the array.

Code

go

package main

import "fmt"

func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}

func main() {
    arr := []int{5, 2, 9, 1}
    insertionSort(arr)
    fmt.Println(arr)
}

Output

[1 2 5 9]

Dry Run

Let's trace the array [5, 2, 9, 1] through the insertion sort code.

1

Start with i=1, key=2

Compare 2 with 5; since 5 > 2, shift 5 right. Array becomes [5, 5, 9, 1]. Insert 2 at position 0. Array now [2, 5, 9, 1].

2

i=2, key=9

Compare 9 with 5; 5 < 9, no shift needed. Insert 9 at position 2. Array remains [2, 5, 9, 1].

3

i=3, key=1

Compare 1 with 9; shift 9 right. Compare 1 with 5; shift 5 right. Compare 1 with 2; shift 2 right. Insert 1 at position 0. Array now [1, 2, 5, 9].

Iteration	Array State
Start	[5 2 9 1]
i=1	[2 5 9 1]
i=2	[2 5 9 1]
i=3	[1 2 5 9]

Why This Works

Step 1: Choosing the key element

The element at index i is chosen as the key to insert into the sorted left side.

Step 2: Shifting elements

Elements greater than the key are shifted right to make space for the key.

Step 3: Inserting the key

The key is placed in its correct sorted position after shifting.

Alternative Approaches

Using recursion

go

package main

import "fmt"

func insertionSortRecursive(arr []int, n int) {
    if n <= 1 {
        return
    }
    insertionSortRecursive(arr, n-1)
    key := arr[n-1]
    j := n - 2
    for j >= 0 && arr[j] > key {
        arr[j+1] = arr[j]
        j--
    }
    arr[j+1] = key
}

func main() {
    arr := []int{5, 2, 9, 1}
    insertionSortRecursive(arr, len(arr))
    fmt.Println(arr)
}

Recursion makes the code elegant but uses more stack space.

Using built-in sort package

go

package main

import (
    "fmt"
    "sort"
)

func main() {
    arr := []int{5, 2, 9, 1}
    sort.Ints(arr)
    fmt.Println(arr)
}

Using built-in sort is faster and simpler but does not teach insertion sort 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 the worst case, resulting in O(n^2).

Space Complexity

It sorts the array in place without extra arrays, so space complexity is O(1).

Which Approach is Fastest?

Built-in sort functions are faster due to optimized algorithms; recursive insertion sort is less space efficient than iterative.

Approach	Time	Space	Best For
Iterative Insertion Sort	O(n^2)	O(1)	Small or nearly sorted arrays
Recursive Insertion Sort	O(n^2)	O(n) due to recursion stack	Learning recursion concepts
Built-in sort.Ints	O(n log n)	O(n) or O(1) depending on implementation	General purpose sorting