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 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).

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
R. Gupta

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