Description

It inserts each element into its proper place in the final list.
More efficient than selection sort and bubble sort.

Process of Insertion Sort
1) loop from first element to last element
2) Compare the current element to it's previous element
3) If current element is smaller than the previous elements
   move the greater element one position up
   
Time Complexity:
    Best Case: O(n) - Array already sorted
    Worst Case: O(n2) - Array sorted in reverse order

C/C++

/* C program of Insertion sort */
//Save it as insertionSort.c

#include<stdio.h>
int main(){

    int i,n;

    printf("Enter the size of array : ");
    scanf("%d",&n);

    int arr[n];

    printf("\nEnter element : ");
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }

    insertionSort(arr,n);

    printf("\nThe Sorted array is : ");
    for(i=0;i<n;i++)
    {
        printf("%d ",arr[i]);
    }

    return 0;
}

void insertionSort(int arr[], int n){

    int i,val,j;

    for(i=1;i<n;i++){

        val=arr[i];
        j=i-1;

        while(j>=0 && arr[j]>val){
            arr[j+1]=arr[j];
            j=j-1;
        }
        arr[j+1]=val;
    }
}

Input:
Enter the size of array : 
5
Enter element : 
64
92
34
59
27

Output:
The Sorted array is : 
27 34 59 64 92

Java

/* Java program of Insertion sort */
//Save it as InsertionSort.java


import java.io.*;
import java.util.Scanner;
public class InsertionSort {

    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        
        int i,n;
        
        System.out.println("Enter the size of array : ");
        n = scanner.nextInt();
        
        int arr[] = new int[n];
        
        System.out.println("Enter element : ");
        for(i=0;i<n;i++){
            
        	arr[i] = scanner.nextInt();
        }
        
        insertionSort(arr,n);
        
        System.out.println("\nThe Sorted array is : ");
        for(i=0;i<n;i++){
            
        	System.out.print(arr[i]+ " ");
        }
    }

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

Input:
Enter the size of array : 
5
Enter element : 
64
92
34
59
27

Output:
The Sorted array is : 
27 34 59 64 92

Related Programs