# Sorting Algorithms: Insertion Sort in Golang

Insertion sort is an** In-Place**

*and*

**algorithm. The array elements are compared with each other sequentially and then arranged simultaneously in ascending order. The analogy can be understood from the style we arrange a deck of cards. This sort works on the principle of inserting an element at a particular position, hence the name Insertion Sort. If there is only one item in the list, then it is always sorted. Insertion sort divides the array into 2 parts: one sorted and another unsorted.**

*stable sort***Algorithm Steps:**

**Step 1** − If it is the first element, it is already sorted.

**Step 2** − Pick next element, known as key

**Step 3** − Compare this key with all elements in the sorted sub-list

**Step 4** − Shift all the elements in the sorted sub-list that is greater than the key value

**Step 5** − Insert the key value at appropriate place in sorted list

**Step 6** − Repeat until list is sorted

**Algorithm Working is shown below image:**

Here is the Golang implementation for insertion sort:

package mainimport "fmt"

func Insertion(A *[] int)

{

for j:=1;j<len((*A));j++

{

i:=j-1

key:=(*A)[j]

for i>=0 &&(*A)[i]>key

{

(*A)[i+1]=(*A)[i]

i--

}

(*A)[i+1] = key

}

}func PrintArr(A *[] int){

for i:=0; i<len(*A);i++{

fmt.Printf("A[%d]:%d", i ,(*A)[i])

fmt.Printf("\n")

}

}

func main(){

A:=[]int{11,90,8,9,7,6}

fmt.Println("Array Before Insertion Sort Algorithm---->")

PrintArr(&A)

Insertion(&A)

fmt.Println("Array After Insertion Sort Algorithm---->")

PrintArr(&A)

}

**Insertion Sort Time Complexity:**

*Best case complexity: O(n),* when the given list is sorted in ascending order.*Worst-case complexity: O(n²),* when given list is reverse sorted i.e. in descending order.

**Insertion Sort Space Complexity:**

The algorithm does not use any external memory, i.e. **sorted items occupy the same storage as the original ones, **therefore it is known as an In-Place Sorting Algorithm and given space complexity as O(1).