Insertion Sort

• Insertion sort is a simple sorting algorithm that works similarly to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed in the correct position in the sorted part.
• It is a simple sorting algorithm that builds the final sorted array one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Characteristics of Insertion Sort:

• This algorithm is one of the simplest algorithms with a simple implementation
• Basically, Insertion sort is efficient for small data values
• Insertion sort is adaptive in nature, i.e. it is appropriate for data sets that are already partially sorted.

Algorithm for insertion sort:

The simple steps of achieving the insertion sort are listed as follows :

Step 1 – If the element is the first element, assume that it is already sorted. Return 1.

Step2 – Pick the next element, and store it separately in a Key.

Step3 – Now, compare the key with all elements in the sorted array.

Step 4 – If the element in the sorted array is smaller than the current element, then move to the next element. Else, shift greater elements in the array towards the right.

Step 5 – Insert the value.

Step 6 – Repeat until the array is sorted.

Working of Insertion sort Algorithm:

Let’s take an unsorted array. To understand the insertion sort with an example:

Step 1:

Initially, the first two elements are compared in insertion sort.

Here, 31 is greater than 12. That means both elements are already in ascending order. So, for now, 12 is stored in a sorted sub-array.

Step 2:

Now, move to the next two elements and compare them.

Here, 25 is smaller than 31. So, 31 is not at correct position. Now, swap 31 with 25. Along with swapping, insertion sort will also check it with all elements in the sorted array.

Step 3:

Now, two elements in the sorted array are 12 and 25. Move forward to the next elements that are 31 and 8.

Both 31 and 8 are not sorted. So, swap them.

After swapping, elements 25 and 8 are unsorted. So swap them.

Now, elements 12 and 8 are unsorted. So swap them.

Now ,the next elements that are 32 and 17are unsorted. So swap them.

Step 4:

After swapping again array becomes unsorted. So, repeating the above process until the array becomes sorted.

So, the final sorted array is:

Implementation of insertion sort:

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("Original array:");
        printArray(arr);
        
        insertionSort(arr);
        
        System.out.println("Sorted array:");
        printArray(arr);
    }

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

            /* Move elements of arr[0..i-1], that are
               greater than key, to one position ahead
               of their current position */
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; ++i) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Output:

Original array:
12 11 13 5 6 
Sorted array:
5 6 11 12 13 

Complexity Analysis of Insertion Sort:

Time Complexity of Insertion Sort:

• The worst-case time complexity of the Insertion sort is O(N^2)
• The average case time complexity of the Insertion sort is O(N^2)
• The time complexity of the best case is O(N).

Space Complexity of Insertion Sort:

The auxiliary space complexity of Insertion Sort is O(1)