Insertion Sort

Insertion Sort is a simple and intuitive sorting algorithm, ideal for beginners to understand the basic concepts of sorting. It builds a sorted sequence by inserting elements one by one into their correct positions in the already sorted part. This article explains the principle and steps of Insertion Sort in detail, providing code examples in C and Go to help beginners get started quickly.

Principle

The core idea of Insertion Sort is:

1. Start from the second element of the array, assuming the first element is the sorted part.
2. Take the current element and compare it with the elements in the sorted part from right to left to find its correct insertion position.
3. Shift all elements in the sorted part that are greater than the current element one position to the right to make space for the current element.
4. Insert the current element into its correct position.
5. Repeat the above steps until the entire array is sorted.

Its time complexity is O(n²), where n is the length of the array. Although it is less efficient than Quick Sort or Merge Sort in practice, its simplicity and efficiency on small-scale data make it an ideal choice for learning algorithms.

Steps

Assuming we want to sort an integer array in ascending order, here are the detailed steps for Insertion Sort:

1. Initialization: Treat the first element of the array as the sorted part and start processing from the second element.
2. Select Element: Take the first element from the unsorted part as the current element.
3. Compare and Shift: Compare the current element with the elements in the sorted part from right to left. If an element in the sorted part is greater than the current element, shift it one position to the right.
4. Insert: Insert the current element into its correct position.
5. Repeat: Repeat steps 2-4 for the remaining unsorted elements until the entire array is sorted.

Implementation

C

Here is the C implementation of Insertion Sort, with detailed comments to aid understanding.

main.c

#include <stdio.h>

// Function to perform insertion sort
void insertionSort(int arr[], int n) {
    int i, j, key;
    
    // Start from the second element
    for (i = 1; i < n; i++) {
        key = arr[i]; // Select the current element
        j = i - 1;   // Index of the last element in the sorted part
        
        // Shift elements greater than key to the right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // Insert key into its correct position
        arr[j + 1] = key;
    }
}

// Helper function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Main function to test insertion sort
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original array: ");
    printArray(arr, n);
    
    insertionSort(arr, n);
    
    printf("Sorted array: ");
    printArray(arr, n);
    
    return 0;
}

Compile & Run

$ gcc -o bin/insertion-sort main.c
$ bin/insertion-sort 
Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90 
$ 

Go

Here is the Go implementation of Insertion Sort, with detailed comments to aid understanding.

main.go

package main

import "fmt"

// insertionSort implements the insertion sort algorithm
func insertionSort(arr []int) {
    n := len(arr)
    
    // Start from the second element
    for i := 1; i < n; i++ {
        key := arr[i] // Select the current element
        j := i - 1    // Index of the last element in the sorted part
        
        // Shift elements greater than key to the right
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        
        // Insert key into its correct position
        arr[j+1] = key;
    }
}

// printArray prints the elements of an array
func printArray(arr []int) {
    for _, val := range arr {
        fmt.Printf("%d ", val)
    }
    fmt.Println()
}

func main() {
    // Example array
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    
    fmt.Print("Original array: ");
    printArray(arr)
    
    insertionSort(arr)
    
    fmt.Print("Sorted array: ");
    printArray(arr)
}

$ gsk build -v
create insertion-sort/bin/insertion-sort-linux-amd64
$ ./bin/insertion-sort-linux-amd64 
Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90

Summary

The core of Insertion Sort is to sort an array by inserting elements from the unsorted part one by one into their correct positions in the already sorted part.

---

Copyright Notice: Freely reproduced, non-commercial, no derivatives, attribution, and keep the source.

Author: afxcn

Source: https://gostartkit.com/docs/algo/insertion-sort

Date Published: June 28, 2025