Insertion sorting is a simple and efficient sorting algorithm used in data structures. It is based on the concept of inserting elements into an already sorted list. This algorithm is particularly useful when dealing with small lists or when the list is nearly sorted.

## How does Insertion Sorting work?

The insertion sorting algorithm works by dividing the input list into two parts: a sorted part and an unsorted part. Initially, the sorted part contains only the first element of the input list, while the unsorted part contains the remaining elements.

For each iteration, the first element in the unsorted part is picked and inserted into its correct position in the sorted part. This process continues until all elements in the unsorted part are inserted, resulting in a fully sorted list.

## Step-by-step guide to Insertion Sorting:

**Step 1:**Assume that the first element of the list is already sorted.**Step 2:**Take the first element from the unsorted part and compare it with each element in the sorted part from right to left.**Step 3:**If an element in the sorted part is greater than the current element from the unsorted part, shift it one position to the right.**Step 4:**Repeat Step 3 until you find an element that is smaller than or equal to the current element from the unsorted part.**Step 5:**Insert the current element from the unsorted part into its correct position in the sorted part.**Step 6:**Repeat Steps 2-5 until all elements in the unsorted part are inserted.

## Example:

Let’s consider an example to understand the insertion sorting algorithm better. Suppose we have an unsorted list of numbers: 5, 2, 4, 6, 1, 3.

**Step 1:** Initially, the sorted part contains only the first element (5), and the unsorted part contains the remaining elements (2, 4, 6, 1, 3).

**Step 2:** Take the first element from the unsorted part (2) and compare it with each element in the sorted part (5).

**Step 3:** Since there is only one element in the sorted part (5) and it is greater than the current element from the unsorted part (2), we shift it one position to the right.

**Step 4:** Now we compare the current element from the unsorted part (2) with each element in the sorted part (5).

**Step 5:** The current element from the unsorted part (2) is smaller than the first element in the sorted part (5). So we insert it into its correct position in the sorted part.

**New Sorted Part:** __2__, __5__

**New Unsorted Part:** __4__, __6__, __1__, __3__

**Note:**The elements in bold are now a part of our sorted list.

**Step 6:** Repeat Steps 2-5 until all elements in the unsorted part are inserted.

**Step 2:** Take the first element from the unsorted part (4) and compare it with each element in the sorted part (2, 5).

**Step 3:** The current element from the unsorted part (4) is greater than the second element in the sorted part (5). So no shifting is required.

**Step 4:** Now we compare the current element from the unsorted part (4) with each element in the sorted part (2, 5).

**Step 5:** The current element from the unsorted part (4) is smaller than the second element in the sorted part (5).

**New Sorted Part:** __2__, __4__, __5__

**New Unsorted Part:** __6__, __1__, __3__

This process continues until all elements from the unsorted part are inserted into their correct positions. Finally, we obtain a fully sorted list: 1, 2, 3, 4, 5, 6.

## Time Complexity of Insertion Sorting:

The time complexity of insertion sorting algorithm is O(n^2) in worst-case and average-case scenarios. However, it performs significantly better when dealing with small lists or nearly sorted lists. In such cases, its time complexity can be close to O(n), making it an efficient choice.

### Conclusion:

Insertion sorting is a simple and efficient algorithm used for sorting elements in data structures. It works by inserting elements into an already sorted list, resulting in a fully sorted list.

This algorithm is particularly useful when dealing with small lists or when the list is nearly sorted. By understanding the concept and steps involved in insertion sorting, you can effectively use it to sort your data and improve the efficiency of your programs.