Insertion Sort | CrackEase

Insertion Sort

Insertion_Sort.png

Insertion Sort

Insertion sort builds the final sorted array one item at a time. For each element it picks (called the key), it inserts the key into the correct position among the previously sorted elements.

The algorithm is inspired by how people sort playing cards in their hands — pick a card and insert it into the correct place among the cards you already hold.

At any step the array is conceptually split into a sorted part (left) and an unsorted part (right). Each iteration takes the first element from the unsorted part and inserts it into the sorted part.

Approach of Insertion Sort

Iterate the array from the second element to the end (index 1 to n-1).
Take the current element as key and compare it with elements in the sorted portion to its left.
Shift elements greater than key one position to the right to make space.
Insert the key into the correct position.

Code of Insertion Sort

  
#include <stdio.h>

// Function to print array 
void display(int arr[], int size) 
{ 
    int i; 
    for (i = 0; i < size; i++) 
        printf("%d ", arr[i]); 
    printf("\n"); 
} 

// Main function to run the program
int main() 
{ 
    int array[] = {8, 6, 4, 20, 24, 2, 10, 12}; 
    int size = sizeof(array)/sizeof(array[0]); 

    printf("Before Insertion sort: \n");
    display(array, size);

    int i, key, j;  
    for (i = 1; i < size; i++) 
    { 
        key = array[i]; 
        j = i - 1; 

        /* Move elements of array[0..i-1], that are greater than key,
           to one position ahead of their current position */ 
        while (j >= 0 && array[j] > key) 
        {  
            array[j + 1] = array[j];  
            j = j - 1;  
        }
        // place key at correct position
        array[j + 1] = key;  
    }

    printf("After Insertion sort: \n"); 
    display(array, size); 

    return 0; 
}
// Time Complexity : O(n^2) (avg & worst), O(n) best
// Auxiliary Space : O(1)

  
// C++ Program for Insertion Sort
// Time Complexity : O(n^2) (average & worst), O(n) best
// Space Complexity : O(1)
#include <iostream>
using namespace std;

// Function to print array.
void display(int arr[], int size) 
{ 
    for (int i = 0; i < size; i++) 
        cout << arr[i] << "\t"; 
    cout << "\n"; 
} 

// Main function to run the program.
int main() 
{ 
    int array[] = {8, 6, 4, 20, 24, 2, 10, 12}; 
    int size = sizeof(array)/sizeof(array[0]); 

    cout << "Before Insertion sort: \n";
    display(array, size);

    int i, key, j;  
    for (i = 1; i < size; i++) { 
        key = array[i]; 
        j = i - 1; 

        // Move elements greater than key to one position ahead
        while (j >= 0 && array[j] > key) 
        {  
            array[j + 1] = array[j];  
            j = j - 1;  // moving backwards
        }
        // place key item now
        array[j + 1] = key;  
    }
    cout << "After Insertion sort: \n"; 
    display(array, size);

    return 0; 
}

  
// Java Program for Insertion Sort
// Time Complexity : O(n^2) (average & worst), O(n) best
// Space Complexity : O(1)
class Main
{
    // Main method
    public static void main(String args[])
    {
        int a[] = {8, 6, 4, 20, 24, 2, 10, 12};

        System.out.println("Before Insertion Sort: ");
        printArray(a);

        insertionSort(a);

        System.out.println("After Insertion Sort: ");
        printArray(a);
    }

    /*Function to sort array using insertion sort*/
    static void insertionSort(int arr[])
    {
        int len = arr.length; // calculating the length of the array
        for (int i = 1; i < len; i++) 
        { 
            int key = arr[i]; 
            int j = i - 1; 

            /* Shift elements of arr[0..i-1], that are greater 
               than key, to one position ahead of their current position */ 
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    /* A utility function to print array of size n*/
    static void printArray(int a[])
    {
        int len = a.length;
        for (int i = 0; i < len; ++i)
            System.out.print(a[i] + " ");
        System.out.println();
    }
}

	
Before Insertion sort: 
8 6 4 20 24 2 10 12 
After Insertion sort: 
2 4 6 8 10 12 20 24

Advantages and Disadvantages of Insertion Sort

Advantages

Simple and easy to implement.
In-place sorting with O(1) extra space.
Efficient for small or nearly-sorted datasets (best-case O(n)).
Adaptive: performs well when input is partially sorted.

Disadvantages

Poor average and worst-case time complexity O(n²).
Too many shifts for large datasets.
Not suitable for large unsorted arrays.

Properties

Best case: already sorted → O(n).
Worst case: reverse-sorted → O(n²).

Time Complexity for Insertion Sort

Best	Average	Worst	Space Complexity
O(n)	O(n²)	O(n²)	O(1)

Footer Content | CrackEase

→

←

Courses

Chapters

Data Structure

Sorting

Linked List

Stack

Queue

Tree

Insertion Sort

Insertion Sort