Sorting Algorithm - Insertion Sort

Insertion Sort

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

For Example:

Algorithm:

// Sort an arr[] of size n
insertionSort(arr, n);
Loop from i = 1 to n-1.
Pick element arr[i] and insert it into sorted sequence arr[0…i-1]

Another Example: 

12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 5 (Size of input array)
i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6
i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6
i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6
i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13

Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class InsertionSortApp
{
public void printArray(int arr[])
{
for(int i=0;i<arr.length;i++)
{
System.out.println(arr[i] + " ");
}
System.out.println(" ");
}

public void insertionSort(int arr[])
{
       int n = arr.length;
     
       for (int i=1; i<n; ++i)
       {
           int key = arr[i];
           int j = i-1;

           while (j>=0 && arr[j] > key)
           {
               arr[j+1] = arr[j];
               j = j-1;
           }
           arr[j+1] = key;
       }
}

public static void main(String[] args)
{
       int arr[] = {12, 11, 13, 5, 6};
               InsertionSortApp ob = new InsertionSortApp();      
              ob.insertionSort(arr);  
              ob.printArray(arr);
}
}

Output:

5
6
11
12
13

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.

Algorithmic Paradigm: Incremental Approach

Sorting In Place: Yes

Stable: Yes

Uses: Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.