Golang Insertion Sort Algorithm

1. Introduction

Insertion Sort is a comparison-based sorting algorithm. At each step, the algorithm takes one element from the unsorted part and finds its correct position within the sorted part, shifting all larger elements to make space for it. This method mimics the way we often sort playing cards in our hands.

2. Implementation Steps

1. Start from the second element (index 1), as the first element is considered as the initial sorted sublist.

2. For each element, compare it with the elements before it in the sorted sublist.

3. If the current element is smaller than the previous element, shift the larger elements to make space for the current element.

4. Insert the current element in its correct position within the sorted sublist.

5. Repeat the process for all elements in the array.

3. Implementation in Golang

package main
import (
	"fmt"
)
func InsertionSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		key := arr[i]
		j := i - 1
		// Move elements of arr[0..i-1] that are greater than key
		// to one position ahead of their current position
		for j >= 0 && arr[j] > key {
			arr[j+1] = arr[j]
			j = j - 1
		}
		arr[j+1] = key
	}
}
func main() {
	data := []int{64, 34, 25, 12, 22, 11, 90}
	fmt.Println("Original array:", data)
	InsertionSort(data)
	fmt.Println("Sorted array:  ", data)
}

Output:

Original array: [64 34 25 12 22 11 90]
Sorted array:   [11 12 22 25 34 64 90]

Explanation:

1. The InsertionSort function sorts an array using the insertion sort algorithm.

2. For every index i, starting from 1, the algorithm compares the element at index i with the previous elements.

3. If the current element (key) is smaller than its preceding element, the preceding elements are shifted to the right to make space for key.

4. The key is then placed in its correct position within the sorted sublist.

5. The process is repeated until the entire array is sorted.

6. The main function initializes an array, displays its original state, sorts it using InsertionSort, and then displays the sorted state.

Insertion Sort is adaptive, stable, and requires O(1) extra space. While it performs well for small lists or lists that are mostly sorted, it has a worst-case time complexity of O(n^2) for larger or unsorted lists.