Insertion Sort in Java

Insertion sort is a sorting algorithm that places an unsorted element in a sorted list in each iteration.Insertion sort works similar to sorting cards in our hand in a card game in which we place the first card which is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right else we place it to the left. In the same way, other unsorted cards are placed and put in their right place. A similar approach is used by insertion sort.

Algorithm of Insertion Sort :

1) Variable declared i=1
2) Traverse the Array till i<N
3) If arr[i]<arr[i-1] then arr[j]=value present after shifting the elements of the array from j to i-1.
4) Return the Sorted Array.



Advantages of Insertion Sort:

1) Insertion Sort is Simple and easy to implement.
2) Insertion Sort is a stable sorting algorithm.
3) Insertion Sort is efficient for small lists and nearly sorted lists.
4) Insertion Sort is space-efficient as it is an in-place algorithm.
5) Insertion Sort is adaptive in which the number of inversions is directly proportional to number of swaps. For example, no swapping happens for a sorted array and it takes O(n) time only.


Disadvantages of Insertion Sort:

1) Insertion Sort is inefficient for large lists.
2) Insertion Sort is not as efficient as other sorting algorithms (e.g., quick sort,merge sort) for most cases.

Insertion Sort Applications

The insertion sort is used when:

1) the array has a small number of elements
2) there are only a few elements left to be sorted


Time Complexity

Worst Case: O(n^2)

Suppose, an array is in ascending order, and you want to sort it in descending order. In this case, worst case complexity occurs and hence each element has to be compared with each of the other elements so, for every nth element, (n-1) number of comparisons are made and thus making the total number of comparisons = n*(n-1) ~ n2

Best Case: O(n)

When the array is already sorted, the outer loop runs for n number of times whereas the inner loop does not run at all. So, there are only n number of comparisons making complexity linear.

Average Case: O(n^2)

It occurs when the elements of an array are neither in ascending nor descending order.


Space Complexity : O(1)

Space complexity is O(1) because an extra variable key is used.

Program 1 : Insertion Sort in Java

public class InsertionSort {

	public static  void sort(int arr[])
    {
        int arr_size = arr.length;
        for (int i = 1; i < arr_size; ++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 a[] = { 15, 10, 28, 75, 30 };

        InsertionSort obj_insertion = new InsertionSort();
        obj_insertion.sort(a);

        int n = a.length;
        System.out.print("Sorted Elements in Array are : " + "\n");

        for (int i = 0; i < n; ++i)
            System.out.print( a[i] + " ");

    }
}
Output :

Sorted Elements in Array are : 
10 15 28 30 75
Scroll to Top