1. Introduction

Insertion Sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages such as simple implementation and efficient for small datasets or lists that are mostly sorted.

2. Program Steps

1. Begin from the second element (consider the first element as sorted).

2. Compare the current element with the previous element.

3. If the current element is smaller than the previous element, compare it with the elements before it. Move each of the compared elements up to make space for the swapped element.

4. Repeat the process until the correct position for the current element is found and insert it there.

5. Move to the next element and repeat the above steps.

3. Code Program

public class InsertionSort {

    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 main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.println("Sorted array:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Output:

Sorted array:
5 6 11 12 13

4. Step By Step Explanation

1. The function insertionSort takes an integer array arr as its argument.

2. For each element, starting from the second one (since the first one is considered sorted), the algorithm compares it to the ones before it.

3. If the current element (key) is smaller than its predecessor, it keeps comparing with the elements before until it reaches an element smaller than it or until it reaches the start of the array.

4. During this process, each of the compared elements is shifted to the right to make space for the key.

5. Once the correct position is found for key, it is placed in its proper position.

6. The algorithm then moves to the next element and repeats the process.

7. The main method is for demonstrating the sorting of a sample array using the insertionSort method and then prints the sorted array.

Insertion Sort is adaptive, meaning it becomes more efficient if the list is partially sorted. While it is less efficient on larger lists compared to other algorithms, its simplicity makes it useful for smaller lists.