Insertion sort is another simple sorting algorithm that builds the final sorted array one element at a time. It iterates through the list and repeatedly inserts each unsorted element into its correct position in the already sorted part of the array.

Here’s how the basic insertion sort algorithm works:

1. Initialization: Start with an unsorted list of elements.
2. Iteration: Iterate through the list, starting from the second element (index 1).
3. Insertion: For each element, compare it with the elements to its left in the sorted part of the array.
4. Shift and Insert: Shift elements greater than the current element one position to the right to make space for the current element, then insert the current element into its correct position.
5. Repeat: Repeat steps 2-4 until all elements are in their correct positions.

import java.util.Arrays;

 class InsertionSort {
    public static void main(String[] args) {
        int[] array = {8,4,2,9,12,5};
        sort(array);
    }

    public static void sort(int[] array){
        for (int i = 1; i < array.length; i++) {
            for(int j=i; j>0; j--){
                if(array[j] < array[j-1]) {
                    int temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                }
            }
            System.out.println(Arrays.toString(array));
        }
    }
 }

Now, let’s illustrate this with a step-by-step example using the array {8, 4, 2, 9, 12, 5}:

• Pass 1 (i=1):
  • The inner loop compares 4 with 8 and swaps them. The array becomes {4, 8, 2, 9, 12, 5}.
  • The array is printed: [4, 8, 2, 9, 12, 5].
• Pass 2 (i=2):
  • The inner loop compares 2 with 8 and swaps them. The array becomes {4, 2, 8, 9, 12, 5}.
  • The inner loop then compares 2 with 4 and swaps them. The array becomes {2, 4, 8, 9, 12, 5}.
  • The array is printed: [2, 4, 8, 9, 12, 5].
• Pass 3 (i=3): The array remains unchanged: [2, 4, 8, 9, 12, 5].
• Pass 4 (i=4): The array remains unchanged: [2, 4, 8, 9, 12, 5].
• Pass 5 (i=5):
  • The inner loop compares 5 with 12 and swaps them. The array becomes {2, 4, 8, 9, 5, 12}.
  • The inner loop then compares 5 with 9 and swaps them. The array becomes {2, 4, 8, 5, 9, 12}.
  • The inner loop then compares 5 with 8 and swaps them. The array becomes {2, 4, 5, 8, 9, 12}.
  • The array is printed: [2, 4, 5, 8, 9, 12].

Here are the key points to remember about insertion sort:

1. Basic Idea: Insertion sort builds the final sorted array one element at a time by repeatedly inserting each unsorted element into its correct position in the already sorted part of the array.
2. Iteration: It iterates through the list, starting from the second element (index 1), and compares each element with the elements to its left in the sorted part of the array.
3. Insertion Process: For each element, it compares it with the elements to its left in the sorted part of the array and shifts elements greater than the current element one position to the right to make space for the current element. Then, it inserts the current element into its correct position.
4. Time Complexity: Insertion sort has a time complexity of O(n^2) in the worst case and average case, where n is the number of elements in the list. This makes it suitable for small datasets or nearly sorted lists.
5. In-Place Sorting: It is an in-place sorting algorithm, meaning it sorts the list without requiring extra space proportional to the size of the input array.
6. Stability: Insertion sort is a stable sorting algorithm, preserving the relative order of equal elements.
7. Adaptability: Insertion sort performs well on partially sorted lists or small datasets. It adapts quickly to lists where only a few elements are out of order.
8. Efficiency: While insertion sort is simple and easy to implement, it is not as efficient as some other sorting algorithms, such as quicksort or mergesort, for large datasets due to its quadratic time complexity.