# 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.