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.

Practice

1. What is the main idea behind the Insertion Sort algorithm?

easy

A. Divide the array into halves and sort each half recursively

B. Build the sorted array one element at a time by inserting elements into their correct position

C. Swap adjacent elements if they are in wrong order repeatedly

D. Select the smallest element and swap it with the first unsorted element

Solution

1. Step 1: Understand insertion sort process

   Insertion sort builds the sorted list by taking one element at a time and placing it in the correct position relative to the already sorted part.

2. Step 2: Compare with other sorting methods

   Other options describe merge sort (B), bubble sort (C), and selection sort (D), which are different algorithms.

3. Final Answer:

   Build the sorted array one element at a time by inserting elements into their correct position -> Option B

4. Quick Check:

   Insertion sort = Insert elements step-by-step [OK]

Hint: Insertion sort inserts elements one by one in order [OK]

Common Mistakes:

• Confusing insertion sort with bubble or selection sort
• Thinking insertion sort divides array recursively
• Assuming insertion sort swaps all elements repeatedly

2. Which of the following Go code snippets correctly starts the outer loop for insertion sort on a slice arr?

easy

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

B. for i := 0; i < len(arr); i++ {

C. for i := len(arr)-1; i >= 0; i-- {

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

Solution

1. Step 1: Identify correct loop start for insertion sort

   Insertion sort starts from the second element (index 1) because the first element is considered sorted.

2. Step 2: Check loop conditions

   Loop runs while i is less than length of array. for i := 1; i < len(arr); i++ { matches this exactly.

3. Final Answer:

   for i := 1; i < len(arr); i++ { -> Option A

4. Quick Check:

   Start from index 1 to end [OK]

Hint: Start outer loop at 1, not 0, for insertion sort [OK]

Common Mistakes:

• Starting loop at 0 instead of 1
• Using <= instead of < in loop condition
• Looping backwards incorrectly

3. What will be the output slice after running insertion sort on arr := []int{4, 3, 2, 1}?

medium

A. [1, 3, 2, 4]

B. [4, 3, 2, 1]

C. [1, 2, 3, 4]

D. [2, 3, 4, 1]

Solution

1. Step 1: Trace insertion sort on given array

   Start with 4 (sorted). Insert 3 before 4 -> [3,4,2,1]. Insert 2 before 3 -> [2,3,4,1]. Insert 1 before 2 -> [1,2,3,4].

2. Step 2: Confirm final sorted slice

   The array is sorted in ascending order: [1, 2, 3, 4].

3. Final Answer:

   [1, 2, 3, 4] -> Option C

4. Quick Check:

   Sorted ascending = [1, 2, 3, 4] [OK]

Hint: Insertion sort outputs sorted ascending array [OK]

Common Mistakes:

• Assuming no change in array
• Stopping sorting early
• Mixing up partial sorted states

4. Identify the error in this Go insertion sort snippet:

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] = key
}

medium

A. The outer loop should start from i := 0

B. The inner loop condition should be arr[j] < key

C. The variable key should be declared outside the loop

D. The final assignment should be arr[j+1] = key, not arr[j] = key

Solution

1. Step 1: Analyze inner loop and final assignment

   After shifting elements greater than key, the correct position is j+1, but code assigns key to arr[j], which is incorrect.

2. Step 2: Correct the assignment

   It should be arr[j+1] = key to place key in the right spot after shifting.

3. Final Answer:

   The final assignment should be arr[j+1] = key, not arr[j] = key -> Option D

4. Quick Check:

   Insert key at arr[j+1] after shifting [OK]

Hint: Assign key to arr[j+1], not arr[j], after shifting [OK]

Common Mistakes:

• Assigning key to wrong index after inner loop
• Reversing comparison operator in inner loop
• Starting outer loop at 0

5. Given a slice arr := []int{5, 2, 9, 1, 5, 6}, how many total element shifts occur during insertion sort?

hard

A. 7

B. 6

C. 8

D. 5

Solution

1. Step 1: Trace shifts for each insertion

   Insert 2: shift 5 -> 1 shift
   Insert 9: no shift -> 0 shifts
   Insert 1: shift 9, 5, 2 -> 3 shifts
   Insert 5: shift 9, 5 -> 2 shifts
   Insert 6: shift 9 -> 1 shift

2. Step 2: Sum all shifts

   Total shifts = 1 + 0 + 3 + 2 + 1 = 7 shifts.

3. Step 3: Verify options

   7 is present as 7.

4. Final Answer:

   7 -> Option A

5. Quick Check:

   Count shifts carefully for each insertion [OK]

Hint: Count shifts by tracing each insertion step [OK]

Common Mistakes:

• Counting comparisons instead of shifts
• Missing shifts when multiple elements move
• Confusing shifts with swaps