Insertion sort algorithm

Insertion sort algorithm is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.

It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

This works like the way we sort playing cards in our hands.

Performance

Worst-case performance :- О(n²) comparisons, swaps
Best-case performance :- O(n) comparisons, O(1) swaps
Average performance :- О(n²) comparisons, swaps
Worst-case space complexity :- О(n) total, O(1) auxiliary

Java Program of Insertion Sort Algorithm


package cn.algo.sorting;

public class InsertionSort {

	void insertionSort(int inputArr[]) {
		
        int n = inputArr.length;  
        for (int j = 1; j < n; j++) 
        {  
            int key = inputArr[j];  
            int i = j-1;  
            while ( (i > -1) && ( inputArr[i] > key ) ) {  
            	inputArr[i+1] = inputArr[i];  
                i--;  
            }  
            inputArr[i+1] = key;  
        }  
    }
	
	/* Printing sorted array */
	void printArray(int inputArr[]) {
		int n = inputArr.length;
		for (int i = 0; i < n; ++i)
			System.out.print(inputArr[i] + " ");
		System.out.println();
	}

	public static void main(String args[]) {
		InsertionSort obj = new InsertionSort();
		int inputArr[] = { 80,15,60,30,20,90 };
		
		System.out.println("Input Array before Insertion Sort.");
		obj.printArray(inputArr);
		
		obj.insertionSort(inputArr);
		System.out.println("\nSorted Array after Insertion Sort.");
		obj.printArray(inputArr);
	}
}