Insertion Sort in Java (With Intuition + Dry run + Code)

Why the name insertion sort ?

The name "insertion sort" comes from the way this sorting algorithm works. It maintains a sorted sublist in the lower positions of the list. It iterates through the list, removing one element at a time and finding the correct position to insert it into the sorted sublist. This process continues until the whole list is sorted. The term "insertion" refers to the action of inserting an element into its correct position within the sorted sublist.

Algorithm :

1. Start with the second element (index 1) of the array.
2. Compare this element to the one before it. If the previous element is greater, swap the two elements.
3. Continue comparing the element to the ones before it and swapping as needed until the element is in its correct sorted position.
4. Move to the next element (index 2) and repeat steps 2-3 until the entire array is sorted.

I will show the working of Insertion sort but make sure to dry run using pen & paper📝

Code

 java
public class InsertionSort {
    public static void main(String[] args) {
       // int arr[] = {5, 4, 10, 1, 6, 2};
        int arr[] = {12, 11, 13, 5, 6};
        int n = arr.length;

        for(int i=1; i<n; i++){
            int temp = arr[i];
            int j = i-1;

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

            arr[j+1] = temp;
        }

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

Time Complexity:

• Best Case: O(n)
• Worst Case: O(n^2)

Space Complexity:

O(1)

Wrapping Up:

Now, congrats, you've learned insertion sort 🥳👏
Thanks for reading :)
Feel free to comment and like the post if you found it helpful
Follow for more 🤝 && Happy Coding 🚀

If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7

Comments

[Spandan Sehgal]

Well explained!

[Tanuja V]

Thank you, Spandan