What is Insertion Sort?

We use Insertion Sort when we need to sort an array of let's say "n" numbers given in a random order to a sorted order.

for e.g.{3,5,4,2,1} ~ {1,2,3,4,5}

We may find the operation of selection sort and insertion sort to be more or less the same algorithm. But the difference mainly between the two is that in selection sort we scan the unsorted part of the array to find the minimum element**,** while insertion sort scans the sorted part to find the correct position to place the element. Selection sort requires fewer swaps than insertion sort, but more comparisons.

This brings us to a question:

Why Insertion Sort?

So, now that we have wrapped our mind around what is Insertion Sort.

Why?

Let's consider bubble sort for understanding if you don't know what bubble sort is, it's a simple sorting algorithm wherein we take an array of numbers in random order and sort them in increasing or decreasing ones just by comparing the current element with the next element by applying two for loops this gives us a time complexity of O(n^2) for all case worst case i.e. {n, n-1, . . . . . . . . . . , 3, 2, 1} for best case i.e.{1, 2, 3, 4, 5, . . . . . .,n} and O(1) space complexity.

In Insertion sort for the worst case, it will have a time complexity of O(n^2) and for the best case it will have O(n) that beats the bubble sort algorithm in one aspect and both have space complexity of O(1). Therefore we use Insertion Sort over Bubble sort.

Some benefits of Insertion Sort are:

1)Adaptive: The number of swaps gets reduced if the array is sorted in the middle somewhere or the start (as compared to bubble Sort),

2)Stable Sorting algorithm: A stable sorting algorithm is if it maintains the relative order of numbers in the case of tie i.e. if you need to sort {1, 1, 2, 3} then if you don't change the order of those first two ones then your algorithm is stable, but if you swap them then it becomes unstable, despite the overall result or sorting order remain same. Thereby not increasing the swaps i.e. the time complexity reduces.

3)Works good when the array is partially sorted.

How Does Insertion Sort work?

1. Start with the first element of the array, considering it as the only element in the sorted part of the array.

2. Iterate through the remaining unsorted elements of the array.

3. For each unsorted element, compare it with the elements in the sorted part of the array and insert it into its correct position.

4. Repeat this process until all elements are sorted.

public class Main {

    public static void main(String[] args) {
        int[] arr = {5, 3, 4, 1, 2};
        insertion(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void insertion(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i+1; j > 0; j--) {
                if (arr[j] < arr[j-1]) {
                    swap(arr, j, j-1);
                } else {
                    break;
                }
            }
        }
    }
private static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
}

Conclusion

Insertion sort may not be the fastest sorting algorithm for large datasets, but its simplicity, adaptability, and in-place sorting make it a valuable tool in many scenarios. By understanding how insertion sort works and its performance characteristics, programmers can leverage its strengths to efficiently organize and manipulate data.

If you liked my blog do share it on socials. You can connect with me on linkedin, twitter and github.

Thanks a lot for reading. Have a nice day👾