Insertion Sort

Insertion sort is an in place comparison based sort. It divides the list into two parts, the sorted part on the left and the unsorted part on the right. It works by sequentially picking up unsorted items and insert them into right position in the sorted array.

Insertion sort is not suitable for large data sets as it has average performance but it has better performance than bubble sort and selection sort.

To continue learning more about insertion sort, check out our video on it:  https://www.youtube.com/watch?v=E8svn2Wgri8

Pseudo code:

START

   Take an array or list of size n in arr

       FOR  i = 1 TO i <  n // Loop for the pass

           int key= arr[i];

           j= i-1

              while j >= 0 && arr[j ] > key) // Loop for the comparison

                  arr[j+1] = arr[j]

                      j = j-1;

             END WHILE

           arr[j+1] = key

END FOR

END

JAVA code:

void insertion(int array[]) { 

        int n = array.length; 

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

            int key = array[i]; 

            int j = i-1; 

            while ( (j >=0) && ( array [j] > key ) ) { 

                array [j+1] = array [j]; 

                j–; 

            } 

            array[j+1] = key; 

        }