Insertion sort algorithm is a simple sorting algorithm that builds the final sorted array or list one item at a time. It is called insertion sort because it inserts each element into its proper place in the sorted array or list.

## How Insertion Sort Algorithm Works

Insertion sort algorithm works by taking one element at a time from the unsorted part of the list or array and inserting it into its proper place in the sorted part of the list or array. The algorithm goes through the list or array multiple times until all elements are in their proper places, which means the list or array is sorted.

## Python Implementation of Insertion Sort Algorithm

Here’s an example of implementing the insertion sort algorithm in Python:

```lessCopy code```def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
``````

In the above code, the `insertion_sort` function takes one argument, `arr`, which is the list or array to be sorted. The function uses a `for` loop to go through the list or array multiple times, taking one element at a time from the unsorted part of the list or array and inserting it into its proper place in the sorted part of the list or array. The `while` loop compares the `key` with the previous element in the sorted part of the list or array and inserts the `key` into its proper place in the sorted part of the list or array.

## Example of Insertion Sort Algorithm

Let’s say we have an unsorted list of numbers as follows:

```cssCopy code```arr = [5, 2, 8, 1, 9, 4]
``````

We want to sort this list using the insertion sort algorithm. We can do this by calling the `insertion_sort` function with the list `arr` as an argument:

```scssCopy code```insertion_sort(arr)
``````

After executing this code, the variable `arr` will contain the sorted list:

```csharpCopy code```[1, 2, 4, 5, 8, 9]
``````

• Simple and easy to understand.
• Works well on small datasets.
• Efficient for nearly sorted datasets.

• Inefficient for large datasets.
• Time complexity is O(n^2), where n is the number of elements in the list or array.

## Conclusion

In conclusion, insertion sort algorithm is a simple sorting algorithm that builds the final sorted array or list one item at a time by taking one element at a time from the unsorted part of the list or array and inserting it into its proper place in the sorted part of the list or array. Although it is easy to understand and efficient for nearly sorted datasets, it is inefficient for large datasets and has a time complexity of O(n^2). It is useful for sorting small datasets or for educational purposes.

## FAQs

1. What is the time complexity of insertion sort algorithm?
• The time complexity of insertion sort algorithm is O(n^2), where n is the number of elements in the list or array.
1. What is the difference between insertion sort and bubble sort?
• Insertion sort and bubble sort are both simple sorting algorithms, but insertion sort builds the final sorted array or list one item at a time by taking one element at a time from the unsorted part of array.

For complete list of topic on DATA STRUCTURE AND ALGORITHM click hear