Insertion Sort

Insertion sort is one of the popular sorting algorithm that sorts the given array and builds the sorted array(list). It is much less efficient on large list than more advance algorithms like Quicksort, Heapsort, Mergesort. However there are sill some advantages of using Insertion Sort:

• Simple Implementation
• Efficient for small data set
• Faster than Quicksort for small data list.

Properties of Insertion Sort

• Best Case time complexity : Here the elements are already in sorted array so no shifting of elements takes place. So we only traverse through the elements of array so its time complexity is O(n)
• Worst Case time complexity : Here the elements are in reverse sorted order so for each element shifting takes place. So its time complexity is O(n²).

Insertion Sorting process(source: wikimedia.org)

Insertion Sort Example  

import java.io.*;

import java.util.*;

public class Solution {

    public static void insertionSort(int[] A){
        for(int i = 1; i < A.length; i++){
            int value = A[i];
            int j = i - 1;
            while(j >= 0 && A[j] > value){
                A[j + 1] = A[j];
                j = j - 1;
            }
            A[j + 1] = value;
        }

        printArray(A);
    }


    static void printArray(int[] ar) {
        for(int n: ar){
            System.out.print(n+" ");
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] ar = new int[n];
        for(int i=0;i<n;i++){
            ar[i]=in.nextInt();
        }
        insertionSort(ar);
    }
}