Python Program for Insertion Sort

Overview

Insertion Sort is a stable and in-place sorting algorithm that can be implemented simply and easily which makes it more helpful for sorting nearly-sorted elements. In insertion sort, an array is divided into two sub-arrays:

Sorted
Unsorted,

where we compare and move every item from the unsorted part to the sorted part till the array is sorted.

Introduction to Insertion Sort in Python

Insertion sort is a simple algorithm that works similarly to the way we sort playing cards using both hands. We traverse one by one through all the cards and compare them with each other. The sorted cards would appear on the left of our hand while the unsorted ones would appear on the right until all of them are sorted.

The array which is to be sorted is divided into two sub-arrays: sorted and unsorted. After splitting, comparisons are done for each element in the unsorted array and this continues until each item in the array is sorted.

This sorting algorithm is specially used when the number of elements in an array is less. It is also useful when the input array is almost sorted, and only a few elements are misplaced in the whole array. In terms of efficiency, insertion sort in Python is not so fast because of the use of nested for-loops.

What Do In-place and Stable Mean?

You might have heard a lot that insertion sort is an in-place and stable algorithm but would have also wondered what these two words mean.

In-place: An algorithm is said to be in-place if it requires some extra space without caring for the input size of the array. After sorting is completed, it rewrites the initial memory locations of the elements in the array.
Stable: An algorithm is stated to be stable when the relative order of equal objects from the initial array is managed.

Insertion Sort in Python Algorithm

The algorithm of insertion sort in Python is to sort the array.

If it is the first element, then place it in the sorted sub-array.
Pick the next element.
Compare the picked element with all the elements in sorted sub-array.
Shift all the elements in the sorted sub-array that are greater than the picked element to be sorted.
Insert the element at the desired place.
Repeat the above steps until the array is completely sorted.

Example of Insertion Sort in Python

Take the first element in the sorted array in the following array.

[9, 4, 16, 1, 5]

Since 9 is the first element and has no other elements on its left side, it remains at its own position.
Now, when moving towards 4, 9 is the largest element in the sorted list and is also greater than 4, so move 4 to its correct position which is before 9.
Now, on traversing further we get 16, 9 was the largest element in the sorted list till now but 9 is smaller than 16, so 16 will remain at the same position.
In this step, we check for 1, all the elements on the left side of 1 (i.e in the sorted list) are moved one position forward as all are greater than 1 and then 1 is placed in the first position.
Finally with 5, as 16 (largest element in the sorted list) is greater than 5, move 5 to its correct position which is before 9.

The resultant sorted array after applying Insertion sort is 1,4,5,9,16

Pseudo Code for Insertion Sort

Here's how the algorithm works:

It takes an array A as input.
It iterates through each element of the array, starting with the second element (index 1).
For each element, it compares it to the elements that came before it, shifting them one position to the right until it finds the correct position for the current element.
Once the correct position is found, the current element is inserted into the array.
The sorted array is returned.

Program for Insertion Sort in Python

Below is the Program for Insertion Sort in Python.

Code:

Output:

Explanation:

In the above program, a function named InsertionSort is created that takes an array as an argument.
A for-loop is used to traverse the array from 1 to len(array). In the for-loop, at first, we assigned the ith value element of the array to the temp variable. Therefore, every time the loop iterates the new value will get assigned to the temp variable.
Next, we shifted the elements of array[0 to i-1], which is greater than the temp value, to one position ahead of their current position.
Now, we used the while-loop to check whether the value of j is greater than or equal to 0, and the value is smaller than the first element of the array.
If both conditions are true then move the first element to the first index and reduce the value of j and so on.
At the end, we called the created InsertionSort function and passed the array a, and printed the sorted array as output.

Program for Insertion Sort in Python (Descending Order)

Numbers are said to be in descending order when they are arranged from largest to smallest number. Insertion sort program can be used to sort numbers in descending order by making some changes in the python program.

Code:

Output:

As you can see in the above Insertion Sort program for sorting numbers in descending order we just changed while j >=0 and temp < a[j] to while j >=0 and temp > a[j] in the python program.

Program for Insertion Sort in Python without Using Function

When Should Insertion Sort Be Used?

The Insertion sort in Python is specially used when the number of elements in an array is less. It is also useful when the input array is almost sorted, and only a few elements are misplaced in the whole array.

Insertion sort is more efficient than bubble sort algorithm.

Insertion sort is less complicated as compared to some complex sorting algorithms like (merge sort, quick sort, etc.) which are used to sort larger size arrays.

Time and Space Complexity of Insertion Sort in Python

Since Insertion sort uses nested for-loops it is a slow algorithm that can be extensively slow in the case of larger arrays but still for smaller-size arrays insertion sort can be a great choice.

The Average and Worst case time complexity of the insertion sort is - $O(n^{2})$

The Best case time complexity of the insertion sort is - $O(n)$

The auxiliary space in insertion sort: $O(1)$

Check out this article to learn more about Arrays in Python.

Conclusion

Insertion sort in Python is a stable and in-place but inefficient algorithm that has its advantages and disadvantages as discussed above, but there are more efficient algorithms are available.
Insertion sort uses the concept of splitting the original array into two sub-arrays: sorted and unsorted. Then compares each element in the unsorted array and continues to do so until each item in the array is sorted.
Insertion sort uses nested for-loops it is a slow algorithm that makes the Average and Worst case time complexity of the algorithm to - $O(n^2)$ .