Insertion sort is one of the simple sorting algorithms, during each iteration a newly inserted element takes its original sorted position. The insertion sort algorithm is very efficient for the small size array.

## What is Insertion Sort?

In the insertion sort algorithm, the array is sorted by selecting the unsorted element repeatedly and placing that unsorted element in its right position in the sorted part of an array.

For example, if we have a list of employee names in the unsorted order. Let’s see how to sort that list using the insertion sort algorithm. First, you could start by considering the first employee name as being sorted, and then comparing each subsequent employee name to the employee names already considered sorted, shifting employee names as necessary to make room for the new employee name, until the new employee name is in its proper place in the sorted list. You would repeat this process for each employee’s name in the list until all the employee names are sorted and in the correct order. This process is similar to the way insertion sort works for sorting an array, as it repeatedly selects an element and inserts it into the correct position relative to the elements before it.

### Working of the Insertion Sort with an Example

Let’s take an example to understand the insertion sort algorithm.

arr = [40, 30, 50, 10, 20]

We will consider the above example and see how the insertion sort algorithm works.

**First pass:**

We will consider the first element of the array to be sorted and compare the first element with the second element.

In this case, the first element 40 is greater than the second element 30 so 30 is not at its correct position. Now, we will swap 40 and 30.

In this array, 30 is a part of the sorted sub-array.

**Second pass:**

In this pass, we will move one step ahead and compare the next two elements. We will compare the second element 40 and the third element 50.

In this case, the third element 50 is already greater than the second element 40 so we will not perform any swap. Now, the second element 40 is also part of the sorted sub-array.

**Third pass:**

In this pass, we will move one step ahead and compare the next two elements. We will compare the third element 50 and the fourth element 10.

Here, 50 and 10 are not at its the right position, Thus, we will swap both the elements.

After performing the swap, we will compare 10 with 40 and they are also not at its right position. So we will swap both the elements.

Now, we will compare 10 and 30 and we can see that they are not in the correct position. Thus, we will swap both the elements.

In this array, we can see that 10 is at its correct position.

**Fourth pass:**

In this pass, we will move one step ahead and compare the next two elements. We will compare the fourth element 50 and the fifth element 20.

Here, 50 and 20 are not at its the right position, Thus, we will swap both the elements.

After performing the swap, we will compare 20 with 40 and they are also not at its right position. So we will swap both the elements.

Now, we will compare 20 and 30 and we can see that they are not in the correct position. Thus, we will swap both the elements.

Now, we can see that the array is sorted.

## Algorithm of the Insertion Sort:

Below is the algorithm of the insertion sort.

```
insertion_sort(array):
for i from 1 to length(array) - 1:
j = i
while j > 0 and array[j-1] > array[j]:
swap(array[j], array[j-1])
j = j - 1
return array
```

**Explanation of the above pseudo-code:**

- The function insertion_sort(array) takes an array as its input.
- The outer loop for i from 1 to length(array) – 1 iterate over each element in the array starting from the second element. The purpose of this loop is to select an unsorted element from the array and insert it into its correct position in the sorted portion of the array.
- The inner while loop performs the insertion and shifting of elements in the sorted portion of the array. The loop starts with the j variable being set to the current value of i.
- The condition while j > 0 and array[j-1] > array[j] checks if j is greater than 0 and if the element array[j-1] is greater than array[j]. If this condition is true, it means that the current element is not in its correct position in the sorted portion of the array, and it needs to be inserted.
- The swap(array[j], array[j-1]) function swaps the current element array[j] with the previous element array[j-1]. This shifts the previous element one position to the right, making room for the current element to be inserted.
- The j variable is decremented by 1 using j = j – 1. This allows the inner loop to continue checking the previous elements in the sorted portion of the array until the current element is in its correct position.
- The inner loop continues until the condition while j > 0 and array[j-1] > array[j] is false, indicating that the current element is in its correct position in the sorted portion of the array.
- The outer loop continues until all elements in the unsorted portion of the array have been inserted into their correct positions in the sorted portion of the array.
- The sorted array is returned as the result of the function insertion_sort(array)

## Insertion Sort Python Program

Now, we will learn how to write the insertion sort python program.

# insertion sort python program def insertion_sort(array): for i in range(1, len(array)): j = i while j > 0 and array[j-1] > array[j]: array[j], array[j-1] = array[j-1], array[j] j = j - 1 return array array = [40, 30, 50, 10, 20] print("Array before the Insertion Sort :", array) sorted_array = insertion_sort(array) print("Array after the Insertion Sort :", sorted_array)

**Output:**

```
Array before the Insertion Sort : [40, 30, 50, 10, 20]
Array after the Insertion Sort : [10, 20, 30, 40, 50]
```

In the above insertion sort python code, we have taken an unsorted array. After that, we have sorted that array using the insertion sort python function. In the output, we can see that after performing the insertion sort array is sorted.

**Time Complexity:** O(n^2)

**Space Complexity:** O(1)

**Conclusion:**

In conclusion, this article will help you to understand what is the insertion sort and what is the algorithm of an insertion sort. In addition, you will also learn how to write the insertion sort python program and the time and space complexity of the insertion sort python program.

## FAQs Related to Insertion Sort in Python

**1. Is the Insertion Sort algorithm an in-place sorting algorithm?**

Yes, the Insertion Sort algorithm is an in-place sorting algorithm, meaning that it sorts the input array without using any additional memory.

**2. Is the Insertion Sort algorithm a stable sorting algorithm?**

Yes, the Insertion Sort algorithm is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the sorted array.

**3. Can the Insertion Sort algorithm be used for linked lists?**

Yes, the Insertion Sort algorithm can be used for linked lists, with a slight modification to the implementation. Instead of swapping elements in an array, the elements in the linked list are reordered by adjusting the pointers.

**4. Is the Insertion Sort algorithm suitable for sorting large datasets?**

The Insertion Sort algorithm is not suitable for sorting large datasets due to its O(n^2) time complexity. For large datasets, more efficient algorithms such as QuickSort, MergeSort, or HeapSort should be used.

**5. How does the Insertion Sort algorithm handle arrays with elements of different sizes, such as arrays with integers and strings?**

The Insertion Sort algorithm can be used for sorting arrays with elements of different sizes as long as the comparison between elements is well-defined. For example, arrays with integers and strings can be sorted by defining a comparison based on the ASCII values of the characters in the strings.