Insertion Sort Algorithm in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Insertion Sort on a small array

What is the output of the following Go code that uses insertion sort on the array [4, 3, 2, 1]?

DSA 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{4, 3, 2, 1}
    insertionSort(arr)
    fmt.Println(arr)
}

A [1 3 2 4]

B [4 3 2 1]

C [1 2 3 4]

D [2 3 4 1]

💡 Hint

Insertion sort moves smaller elements to the front step by step.

Insertion sort sorts the array in ascending order by inserting each element into its correct position in the sorted part of the array.

❓ Predict Output

intermediate

Insertion Sort with duplicate elements

What will be the output after running insertion sort on the array [5, 3, 5, 2, 2]?

DSA 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, 3, 5, 2, 2}
    insertionSort(arr)
    fmt.Println(arr)
}

A [5 3 5 2 2]

B [3 2 2 5 5]

C [2 3 5 2 5]

D [2 2 3 5 5]

💡 Hint

Duplicates should be placed next to each other in sorted order.

Insertion sort keeps duplicates in order and sorts the array ascendingly.

🧠 Conceptual

advanced

Time complexity of insertion sort in worst case

What is the time complexity of insertion sort in the worst case scenario?

A O(n^2)

B O(n log n)

C O(n)

D O(log n)

💡 Hint

Worst case happens when the array is sorted in reverse order.

Insertion sort compares each element with all previous elements in worst case, leading to O(n^2) time.

🔧 Debug

advanced

Identify the bug in this insertion sort code

What error will this Go code produce when running insertion sort?

DSA Go

package main
import "fmt"
func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}
func main() {
    arr := []int{3, 1, 2}
    insertionSort(arr)
    fmt.Println(arr)
}

A Runtime panic: index out of range

B [1 2 3]

C [3 1 2]

D Syntax error: missing colon

💡 Hint

Check the initial value of j and array indexing inside the loop.

j starts at i instead of i-1, causing arr[j] to access out of range when j == len(arr).

🚀 Application

expert

Number of shifts in insertion sort for a given array

How many times will elements be shifted (moved) during insertion sort on the array [8, 4, 3, 7, 6]?

A 4

B 6

C 5

D 7

💡 Hint

Count each time an element is moved to the right during sorting.

Shifts happen when elements are moved to make space for the key. Counting carefully gives 6 shifts.