Insertion Sort Algorithm

Last updated on July 13th, 2024 at 10:18 am

We will discuss the Insertion Sort Algorithm, pseudo code, Code implementation of Insertion Sort in C, C++, Java, JavaScript, Python, advantages & disadvantages, and time & space complexity of Insertion Sort.

1. What is Insertion Sort Algorithm?

Insertion Sort is a simple and efficient comparison sort. It is in-place Sorting.

The Insertion Sort inserts each element into its proper position. It chooses one element, inserts it into its position, and shifts the rest of the list by one location. This process is repeated until no input element remains.

The step-by-step procedure is given as follows:

1. Take an element from an unsorted list.
2. Compare that element with a sorted list from right to left.
3. Shift the list.

Here, it is assumed that the first element is already sorted.

2. Pseudocode for Insertion Sort

INSERTION_SORT(A) 
1. for j = 2 to n 
2. key <- A[j] 
3. // Insert A[j] into the sorted sequence A[1..j-1]
4. j <- i–1 
5. while i>0 and A[i]>key 
6. A[i+1] <- A[i] 
7. i <- i–1 
8. A[j+1] <- key

3. Recurrence Relation of Insertion Sort

The Recurrence Relation for Insertion Sort is

(1)  

4. Code Implementation of Insertion Sort

4.1 Insertion Sort in C

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {29, 64, 73, 34, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

4.2 Insertion Sort in C++

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {29, 64, 73, 34, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

4.3 Insertion Sort in Java

public class InsertionSort {
    void insertionSort(int arr[]) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String args[]) {
        int arr[] = {29, 64, 73, 34, 20};
        InsertionSort ob = new InsertionSort();
        ob.insertionSort(arr);
        System.out.print("Sorted array: ");
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

4.4 Insertion Sort in JavaScript

function insertionSort(arr) {
    let n = arr.length;
    for (let i = 1; i < n; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

let arr = [29, 64, 73, 34, 20];
insertionSort(arr);
console.log("Sorted array: " + arr.join(" "));

4.5 Insertion Sort in Python

def insertionSort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key

arr = [29, 64, 73, 34, 20]
insertionSort(arr)
print("Sorted array:", arr)

5. Advantages of Insertion Sort

1. Simple implementation and easy to understand.
2. Efficient for small data sets or nearly sorted data.
3. In-place sorting algorithm, meaning it doesn’t require additional memory.

6. Disadvantages of Insertion Sort

• Inefficient for large data sets. Its average and worst-case time complexity is O(n²), where n is the number of elements.
• Not suitable for data sets with a large number of inversions.

7. Time and Space Complexity of Insertion Sort

Time Complexity
Worst Case	O(n2)
Best Case	O(n)
Average Case	O(n2)
Space Complexity
Worst Case	O(n2) total O(1) auxiliary

FAQs