# Sorting Algorithms: Insertion Sort in Golang

Insertion sort is an In-Place and stable sort 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.

Algorithm Steps:

`Step 1 − If it is the first element, it is already sorted.Step 2 − Pick next element, known as keyStep 3 − Compare this key with all elements in the sorted sub-listStep 4 − Shift all the elements in the sorted sub-list that is greater than the key valueStep 5 − Insert the key value at appropriate place in sorted listStep 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).

--

-- I am interested in learning new technology. Interested in Programming, AI, Data Science and Networking. Love to explore new places.