The Insertion Sort

How Insertion Sort works

Insertion sort is a simple sorting algorithm where the final sorted array is built by traversing through the array, taking one element at a time and placing it at its right location as per the expected sorted array.

Efficiency of insertion sort

Best case (sorted array is provided as input) : O(n)
Worst case(reverse sorted array is provided as input): O(n^2)
Average case : partially sorted array : O(n+d)
where, n = number of elements in the array and d= number of inversions required to sort the array (inversions = shuffling/interchange of array elements)

The more sorted an array is, the lesser would be d (number of inversions) and hence faster would be insertion sort algorithm.
The nature of insertion sort makes it more efficient than many other quadratic sorting algorithms like bubble sort and selection when the list to be sorted is not too huge , also, the more the list to be sorted is near to being sorted (nearly sorted lists), the better this algorithm would perform.

Advantages of insertion sort

• It is simple to implement
• It is quiet efficient for small sets of data
• It is more efficient than most other quadratic sorting algorithms
• It is stable, which means, if there are more than one elements with the same keys, their relative order remains unchanged
• It is in-place. only requires a single extra element, which would count as constant O(1).
• It can sort a list on-the-go, which means, as and when it is taking inputs, it can keep sorting them.

Insertion sort algorithm implementation in java

public class InsertionSort {

    public static int[] insertionSort(int[] arrayToSort) {

        int key;

        for(int i=1; i < arrayToSort.length; i++){

            //within the outer for loop, assign the next element as 'key'.

           //key is the element which is to be placed at its right location within this iteration of loop

            key =  arrayToSort[i];

            //start traversing from the back of the array in the inner for loop

            int j = i-1;

            //traverse through the elements which are greater than key and shift them as and when we   

            //traverse , one space further, to make space for the key at the right location

            for(; j >= 0 && key < arrayToSort[j]; j--){

                //shift the elements greater than key further in the array

                arrayToSort[j+1] = arrayToSort[j];

            }

           //finally place key at its right location

            arrayToSort[j+1] = key;

        }

        

        //print out the sorted array

        System.out.println("Sorted array:");

        System.out.println();

        for(int i=0; i<arrayToSort.length; i++){

            System.out.print(" " + arrayToSort[i] + " ");

        }

        System.out.println();

       

        return arrayToSort;

    }

    public static void main(String[] args) throws NumberFormatException, IOException {

        List<Integer>listToSort = new ArrayList<Integer>();

        //Take input from the console

        InputStreamReader in = new InputStreamReader(System.in);

        BufferedReader br = new BufferedReader(in);

        System.out.println("Input comma separated list of integers and hit enter when done");

        String inputStr = br.readLine();

        String[] splittedInputs = inputStr.split(",");

        for(String str : splittedInputs){

            listToSort.add(Integer.parseInt(str));

        }

        while(!(inputStr = br.readLine()).equals("DONE")){

            listToSort.add(Integer.parseInt(inputStr));

        }

        //call the insertion sort method

        insertionSort(listToSort.toArray());

    }

}

Reverse Insertion Sort

During Insertion sort, the array elements are normally sorted in ascending order (first element of array = smallest and last one = largest). In case of reverse insertion sort, they are sorted in the descending order. Below is a java function for reverse insertion sort implementation :

    private static void reverseInsertionSort(int[] arrayToSort) {
        int key;
        for(int i=1; i < arrayToSort.length; i++){
            key = arrayToSort[i];
            int j = i-1;

           //here's the difference from the actual insertion sort

           //we traverse the array backward in the inner for loop and shift the elements which are 

          //smaller than the given key, to find the right place for the key (we shift the elements 

         //larger than the key, in case of normal insertion sort).
            for(; j >= 0 && key > arrayToSort[j]; j--){
                arrayToSort[j+1] = arrayToSort[j];
            }
            arrayToSort[j+1] = key;
        }
 

         //print out the sorted array

         System.out.println("Selection Sorted array:");
        for(int i=0; i<arrayToSort.length; i++){
            System.out.print(" " + arrayToSort[i] + " ");
        }
    }