Insertion Sort

It is a simple Sorting algorithm which sorts the array by shifting elements one by one. Following are some of the important characteristics of Insertion Sort.

1. It is better than Selection Sort and Bubble Sort algorithms.
2. Its space complexity is less, like Bubble Sorting, insertion sort also requires a single additional memory space.
3. It is Stable, as it does not change the relative order of elements with equal keys

How Insertion Sorting Works

Insertion Sort Fig-1

/**

 * Created by Ali on 9/5/2016.   

 * Uses: Insertion sort is uses when number of elements is small. 

 * Or when input array is almost sorted, only few elements are misplaced in complete big array. 

**/

public class InsertionSort {
    public static void main(String str[]) {
        int[] arr = new int[]{10,54,2,100,200,121,99,150,51,181};
        InsertionSort obj = new InsertionSort();
        int[] sortedArray = obj.insertionSort(arr);
        for (int i = 0; i < sortedArray.length; i++) {
            System.out.print(sortedArray[i] + " ");
        }
    }

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

Time Complexity: O(n*n)

Auxiliary Space: O(1)

Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.