Introduction

Insertion Sort is one of the simplest sorting algorithms. In insertion sort, the input array is broken down into two parts

1. Sorted
2. Unsorted

• Initially sorted part only contains the first element of the array.

• At each step, we pick the next element from the Unsorted part and insert it into the right position in the sorted part.

Time Complexity

• Worst Case- O(n*n)
• Best Case- O(n) – When the array is already sorted

Space Complexity

Space Complexity of insertion sort is O(1)

Implementation:

package main
import "fmt"
func main() {
sample := []int{3, 4, 5, 2, 1}
insertionSort(sample)
sample = []int{3, 4, 5, 2, 1, 7, 8, -1, -3}
insertionSort(sample)
}
func insertionSort(arr []int) {
len := len(arr)
for i := 1; i < len; i++ {
for j := 0; j < i; j++ {
if arr[j] > arr[i] {
arr[j], arr[i] = arr[i], arr[j]
}
}
}
fmt.Println("After Sorting")
for _, val := range arr {
fmt.Println(val)
}
}

Output:

After Sorting
1
2
3
4
5
After Sorting
-3
-1
1
2
3
4
5
7
8