Insertion sort is a sorting algorithm in which the elements are transferred individually to the right position. In other words, an insertion sort helps build the final sorted list, one item at a time, with the movement of higher-ranked elements. It has the benefits of simplicity and low overhead.

The array is searched sequentially, and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst-case complexity is of ÎŸ(n^2 ), where n is the number of items.

What is the Insertion Sort Algorithm?

Insertion sort is an easy comparison-based Sorting algorithm. The insertion sort algorithm starts to compare the first two elements in the array. If the first element is bigger than the second element, they are exchanged with each other. This process is implemented for all neighbor-indexed elements.

Here's an algorithm for Insertion Sort:

insertionSort(array)
mark the first element as sorted
for each unsorted element Xs
â€˜extractâ€™ the element X
for j <- lastSortedIndex down to 0 if current element j > X
move sorted element to the right by 1
break loop and insert X here
end insertionSort

Working of Insertion Sort Algorithm

In the above image, we see the process of inserting elements into a sorted list using the insertion sort algorithm. It starts with the initial sorted list containing only the number 54. As each new element is introduced (e.g., 26, 93, 17, etc.), the algorithm shifts elements as needed to maintain the sorted order. For instance, when inserting 26, it shifts 54 to the right and places 26 at the beginning. This process continues for each subsequent number, demonstrating how insertion sort efficiently builds a sorted list by inserting one item at a time.

Example of Insertion Sort Algorithm

Letâ€™s take an example to understand Insertion Sort Algorithm: Take an array A[] = [ 7, 5, 4, 2 ]

Since 7 is the first element that has no other element to be compared with, it remains at its position. Now when on moving towards 4, 7 is the largest element in the sorted list and greater than 4. So, move 4 to its correct position, i.e., before 7. Similarly, with 5, as 7 (the largest element in the sorted list) is greater than 5, we will move 5 to its correct position. Finally, for 2, all the elements on the left side of 2 (sorted list) are moved one position forward as all are greater than 2, and then two is placed in the first position. Finally, the given array will result in a sorted array.

Implementation of Insertion Sort

C

C++

Python

Java

JavaScript

PHP

C#

C

#include <stdio.h>

void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1;

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;

In both the worst and average scenarios, where 'n' is the number of elements, Insertion Sort has an O(n^2) time complexity. This is because it could, in the worst case, involve nested loops for swaps and comparisons. But in the best scenario (when the list is already sorted), it has an efficient time complexity of O(n).

Since Insertion Sort doesn't need extra memory in proportion to the input size, its space complexity is O(1). Sorting in place or rearranging elements within the current array without allocating new memory. Although Insertion Sort is straightforward and appropriate for small datasets, it loses efficiency when applied to larger datasets compared to more advanced sorting algorithms like Quick Sort or Merge Sort.

Features of Insertion Sort

There are several characteristics of Insertion Sort are discussed below:

Insertion Sort is efficient for smaller data sets but can be inefficient for larger data sets.

Insertion Sort is an adaptive algorithm means it can be used for arrays that are partially sorted appropriately.

Easy and Simple Implementation is also one of the characteristics because every beginner can learn this sorting algorithm.

The space complexity is lesser as we don't have to create extra memory other than the given array of elements that are to be sorted.

In the best case, where the array is already sorted, Time Complexity will be linear O(n).

Advantages of Insertion Sort Algorithm

Simple Implementation: Insertion sort is straightforward to implement and understand, making it a good choice for beginners learning sorting algorithms.

Efficient for Small Datasets: For small arrays or lists, insertion sort performs well compared to more complex algorithms due to its low overhead.

Stable Sorting: Insertion sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements, which is beneficial for certain applications.

Adaptive: The algorithm is adaptive, meaning it performs better on partially sorted data. It requires fewer comparisons and swaps, reducing the time complexity in such cases.

Low Memory Usage: Insertion sort requires minimal additional memory, making it suitable for systems with limited memory resources, as it sorts in place.

Online Algorithm: Insertion sort can sort a list as it receives it, allowing for dynamic data handling where new elements can be added during the sorting process.

Disadvantages of Insertion Sort Algorithm

Inefficiency on Large Datasets: Insertion sort has a time complexity of O(nÂ²) in the average and worst cases, making it inefficient for large datasets compared to more advanced sorting algorithms like quicksort or mergesort.

More Comparisons and Swaps: The algorithm may require many comparisons and swaps, leading to longer execution times for larger lists, especially when elements are in reverse order.

Limited Use Cases: While it is effective for small or partially sorted arrays, insertion sort is not suitable for larger datasets, limiting its practical applications in some scenarios.

Applications of Insertion Sort Algorithm

Small Datasets: Insertion sort is often used for small datasets where its simplicity and efficiency outweigh the drawbacks of its time complexity.

Partially Sorted Data: It is effective for datasets that are already partially sorted, as it can quickly sort them with minimal operations.

Real-Time Systems: Due to its online sorting capability, insertion sort can be used in real-time systems where data is received in a stream and needs immediate sorting.

Adaptive Sorting: In scenarios where elements are frequently added or removed, such as in dynamic data handling, insertion sort can efficiently maintain sorted order.

Sorting Linked Lists: Insertion sort can be particularly efficient for linked lists, as it can easily insert elements without the need for additional memory allocation.

Educational Purposes: Insertion sort is commonly taught in computer science courses to introduce students to basic sorting algorithms and concepts, providing a foundation for understanding more complex algorithms.

Frequently Asked Questions

What is insertion sort steps?

A straightforward sorting algorithm is the insertion sort. Its steps involve repeatedly moving an element from a list's unsorted section to the appropriate spot in the sorted section.

What is the purpose of insertion sorting?

Insertion sorting is used to reorder items in an array into ascending or descending order. It accomplishes this by repeatedly placing elements in the appropriate positions.

What is the difference between selection sort and insertion sort in C?

Selection sort repeatedly selects the smallest element from the unsorted portion and swaps it with the first unsorted element. Insertion sort builds a sorted array by repeatedly inserting the next element into its correct position within the sorted portion.

What is an example of insertion sort?

An example of insertion sort is sorting the array 5,2,9,1,5The algorithm starts with the second element and inserts it into its correct position in the sorted part, resulting in 1,2,5,5,9.

What is the logic of the insertion sorting algorithm?

The logic of the insertion sort algorithm involves iterating through the array, picking each element and comparing it with the elements in the sorted part. It places the selected element in the correct position by shifting larger elements to the right.

Conclusion

Insertion sort isnâ€™t a particularly efficient algorithm, but it is easy to understand and relatively straightforward to write up. There are a handful of different ways to implement it, and I encourage you to take the tests I provided and try to find a different way to implement it.

In this article, we discussed what Insertion sort is, The algorithm of insertion sort, The working of insertion sort, The implementation of Insertion Sort in C, C++, Java, and Python, and the characteristics of Insertion Sort.