Insertion Sort Algorithm - Working Explained (+Code Examples)

15 mins read

Sorting algorithms play a crucial role in computer science, enabling efficient organization and retrieval of data. One such fundamental algorithm is Insertion Sort, which works similarly to how we arrange playing cards in our hands. It builds the sorted list one element at a time by comparing and placing each new element in its correct position.

In this article, we will explore the Insertion Sort algorithm, its working mechanism, time complexity, and implementation in different programming languages. Whether you're a beginner or an experienced programmer, understanding this simple yet effective sorting technique will enhance your grasp of algorithmic problem-solving.

What Is Insertion Sort Algorithm?

Insertion Sort is a simple and efficient sorting algorithm that works similarly to how we sort playing cards in our hands. It builds the sorted array one element at a time by taking each element and placing it in its correct position.

Working Principle Of Insertion Sort

Insertion Sort works as follows:

1. Assume the first element is already sorted.
2. Pick the next element and compare it with the elements in the sorted section (left side).
3. Shift the larger elements one position to the right to make space for the new element.
4. Insert the picked element at its correct position.
5. Repeat steps 2-4 for all elements in the array.

This process continues until the entire array is sorted.

Real-Life Analogy

Imagine you are sorting a deck of playing cards in your hand:

• You pick a card and assume it’s in its correct place.
• You take the next card and insert it into the right position by shifting the other cards if necessary.
• You continue this process, placing each new card in the correct order relative to the ones already sorted.

This is exactly how Insertion Sort works—placing each element in the right position one at a time!

How Does Insertion Sort Work? (Step-by-Step Explanation)

Let's take an example to understand the step-by-step working of Insertion Sort algorithm in data structures.

Example: Sort the array [6, 3, 8, 5, 2] using Insertion Sort.

Step 1: Consider the First Element as Sorted

• The first element 6 is already considered sorted.
• Array state: [6, 3, 8, 5, 2]

Step 2: Pick the Next Element (3) and Insert It in the Sorted Part

• Compare 3 with 6 → Since 3 < 6, shift 6 to the right.
• Insert 3 in the correct position.
• Array state: [3, 6, 8, 5, 2]

Step 3: Pick the Next Element (8) and Insert It in the Sorted Part

• Compare 8 with 6 → 8 > 6, so no shifting is required.
• Array state remains: [3, 6, 8, 5, 2]

Step 4: Pick the Next Element (5) and Insert It in the Sorted Part

• Compare 5 with 8 → Shift 8 to the right.
• Compare 5 with 6 → Shift 6 to the right.
• Insert 5 in the correct position.
• Array state: [3, 5, 6, 8, 2]

Step 5: Pick the Next Element (2) and Insert It in the Sorted Part

• Compare 2 with 8 → Shift 8 to the right.
• Compare 2 with 6 → Shift 6 to the right.
• Compare 2 with 5 → Shift 5 to the right.
• Compare 2 with 3 → Shift 3 to the right.
• Insert 2 in the correct position.
• Array state: [2, 3, 5, 6, 8]

Final Sorted Array: [2, 3, 5, 6, 8]

Pseudocode For Insertion Sort

Here’s a simple pseudocode to understand the logic of Insertion Sort:

InsertionSort(arr, n):
    for i from 1 to n-1:
        key = arr[i]
        j = i - 1
        
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  // Shift elements to the right
            j = j - 1
            
        arr[j + 1] = key  // Insert the key in the correct position

Implementation of Insertion Sort in C++

Let’s now look at a simple C++ program to implement Insertion Sort-

Code Example:

#include <iostream>

using namespace std;

// Function to perform Insertion Sort
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // Pick the current element
        int j = i - 1;

        // Shift elements that are greater than key
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }

        // Insert the key in the correct position
        arr[j + 1] = key;
    }
}

// Function to print the array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) 
        cout << arr[i] << " ";
    cout << endl;
}

// Main function
int main() {
    int arr[] = {6, 3, 8, 5, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    insertionSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Output: 

Original array: 6 3 8 5 2 
Sorted array: 2 3 5 6 8  

Explanation:

In the above code example-

1. We start by including the <iostream> header, which allows us to use input and output operations.
2. The using namespace std; directive enables us to use standard library elements without prefixing them with std::.
3. We define the insertionSort() function, which takes an array and its size as arguments.
4. The sorting process begins with the second element (index 1) since a single-element array is already sorted.
5. For each element, we store its value in key and compare it with the elements before it.
6. If an element is greater than key, we shift it one position to the right to make space for insertion.
7. Once we find the correct position, we insert the key value.
8. The process repeats for all elements, gradually building a sorted section of the array.
9. The printArray() function helps us display the array elements, separated by spaces.
10. In main(), we define an integer array {6, 3, 8, 5, 2} and determine its size using sizeof(arr) / sizeof(arr[0]).
11. We print the original array before sorting.
12. The insertionSort() function is called to sort the array.
13. After sorting, we print the updated array to show the sorted order.
14. The program returns 0, indicating successful execution.

Time And Space Complexity Of Insertion Sort

Let’s now have a look at these aspects of the insertion sort algorithm:

1. Time Complexity

2. Space Complexity

• Space Complexity: O(1) (In-place sorting, no extra memory used except a few variables).
• Stable Sort?  Yes (Preserves the relative order of equal elements).

Advantages Of Insertion Sort Algorithm

Some common advantages of insertion sort are: 

1. Simple and Easy to Implement: The algorithm is straightforward and easy to code.
2. Efficient for Small or Nearly Sorted Data: Performs well when the dataset is already partially sorted.
3. Stable Sorting Algorithm: Maintains the relative order of equal elements.
4. In-Place Sorting: Requires only O(1) extra space (no additional arrays needed).
5. Adaptive Nature: Runs in O(n) time if the array is already sorted, making it faster than other O(n²) algorithms in such cases.

Disadvantages Of Insertion Sort Algorithm

Some common disadvantages of insertion sort are: 

1. Inefficient for Large Datasets: Has a worst-case time complexity of O(n²), making it slow for large inputs.
2. Not Suitable for Highly Unsorted Data: Requires many comparisons and shifts in the worst case (reverse-sorted data).
3. Slower Compared to Advanced Sorting Algorithms: Merge Sort (O(n log n)) and Quick Sort (O(n log n)) perform better for large datasets.

Applications Of Insertion Sort Algorithm

Some of the most common applications of insertion sort are as follows:

1. Small Data Sets: Insertion Sort performs well on small datasets due to its simple implementation and low overhead. For small lists, its simplicity makes it faster than more complex algorithms like Merge Sort or Quick Sort.
2. Nearly Sorted Data: If the input list is already partially sorted or nearly sorted, Insertion Sort performs very efficiently. In such cases, it can be more efficient than algorithms like Merge Sort, which may still take time for splitting and merging.
3. Online Sorting: Insertion Sort is useful in applications where data is received in a continuous stream, and elements need to be inserted in sorted order as they arrive. This is often referred to as online sorting, and Insertion Sort handles such cases very well because it can insert new elements into an already sorted list incrementally.
4. Adaptive Sorting: In scenarios where data is frequently updated (e.g., inserting new records into a sorted list), Insertion Sort can adapt well by adding new elements in their correct positions without re-sorting the entire list.
5. Low Memory Usage: Since Insertion Sort works in-place and requires no extra memory other than a few variables for tracking elements, it is well-suited for environments where memory is limited, such as embedded systems or devices with restricted resources.
6. Educational and Demonstration Purposes: Insertion Sort is often used in educational settings to teach algorithm design and sorting techniques due to its simplicity and intuitive approach. It helps beginners understand how algorithms work by focusing on fundamental concepts like comparisons and element swapping.
7. Data Stream Processing: Insertion Sort can be applied in situations where we need to sort incoming data (e.g., streaming data from sensors or real-time systems) incrementally as each data point arrives, especially when it’s necessary to maintain an always-sorted list.
8. Implementing Other Algorithms: Insertion Sort can be used as a part of more complex algorithms, such as Shell Sort, where the initial sorting steps are performed with a smaller gap and then refined using Insertion Sort for the final ordering.

Comparison With Other Sorting Algorithms

Here's a comparison between Insertion Sort and other popular sorting algorithms like Bubble Sort, Selection Sort, and Merge Sort in terms of efficiency, complexity, and use cases.

1. Insertion Sort Vs Bubble Sort

Key Difference: Insertion Sort is generally faster than Bubble Sort due to fewer comparisons and fewer swaps. Insertion Sort often outperforms Bubble Sort, especially with partially sorted data.

2. Insertion Sort Vs Selection Sort

Key Difference: Insertion Sort is generally more efficient than Selection Sort in terms of the number of swaps required. Selection Sort makes a fixed number of swaps (n-1 swaps for n elements), while Insertion Sort makes fewer swaps when the data is nearly sorted.

3. Insertion Sort Vs Merge Sort

Key Difference: Merge Sort is much more efficient than Insertion Sort for large datasets due to its O(n log n) time complexity. However, Insertion Sort has the advantage of being in-place (no extra memory needed), while Merge Sort requires additional memory for merging.

Conclusion 

Insertion Sort is a simple and intuitive sorting algorithm that works well for small datasets or when the data is already nearly sorted. Its in-place and stable nature makes it suitable for specific applications where space is limited or maintaining the relative order of equal elements is important. However, due to its O(n²) time complexity, it is not the most efficient choice for large datasets compared to more advanced algorithms like Quick Sort or Merge Sort.

Despite its limitations, Insertion Sort’s adaptive nature, ease of implementation, and real-world usability in certain scenarios ensure its relevance, especially in scenarios involving dynamic data or small collections. By understanding its strengths and weaknesses, we can apply Insertion Sort effectively in situations where it shines, offering a balance of simplicity and efficiency. 

Frequently Asked Questions

Q. How does the Insertion Sort algorithm work?

The Insertion Sort algorithm sorts an array by repeatedly picking the next element and inserting it into its correct position in the already sorted portion of the array. It begins with the second element and compares it to the elements before it, shifting elements as needed to make space for the new element. This process is repeated for each element until the entire array is sorted.

Step-by-Step Process:

1. Start with the second element (since the first element is trivially sorted).
2. Compare the current element with the one before it.
3. If the current element is smaller, shift the previous element to the right.
4. Continue shifting elements until the current element is greater than or equal to the shifted element, then place it in its correct position.
5. Move to the next element and repeat the process.

The sorting is done in-place, meaning no additional memory is required apart from a few variables for tracking elements.

Q. What is the time complexity of Insertion Sort?

The time complexity of Insertion Sort depends on the state of the input data.

• Best Case (O(n)): When the array is already sorted or nearly sorted, the algorithm only performs a linear scan to insert each element. No shifting occurs in this case, making it a highly efficient operation.
• Worst Case (O(n²)): When the array is sorted in reverse order, each element must be compared and shifted past every other element, resulting in quadratic time complexity.
• Average Case (O(n²)): Typically, the algorithm performs a number of comparisons and shifts proportional to n² for a randomly ordered list.

Although the worst and average case time complexities are O(n²), Insertion Sort’s best-case performance makes it a good choice for small or nearly sorted datasets.

Q. Is Insertion Sort stable?

Yes, Insertion Sort is a stable sorting algorithm. A stable sorting algorithm preserves the relative order of elements with equal values. For instance, if two elements have the same value, Insertion Sort ensures that their relative order remains unchanged after sorting. This property is important in scenarios where the relative order of identical elements carries significance.

For example, consider an array of tuples where each tuple contains a number and a string:

[(1, 'A'), (1, 'B'), (2, 'C')]. After sorting, the relative order of (1, 'A') and (1, 'B') remains intact because of the stability of Insertion Sort.

Q. How does Insertion Sort compare to other sorting algorithms in terms of memory usage?

One of the key advantages of Insertion Sort is its in-place sorting capability, meaning it requires O(1) extra space. Unlike algorithms such as Merge Sort, which require additional space for merging subarrays, Insertion Sort only requires a constant amount of extra memory for temporary variables during element comparisons and shifts.

In scenarios where memory is constrained (e.g., embedded systems or small devices), Insertion Sort is a preferable choice because of its minimal memory overhead.

Q. When is Insertion Sort the best sorting algorithm to use?

Insertion Sort is ideal in the following scenarios:

• Small Datasets: For small arrays or lists, Insertion Sort is efficient due to its low overhead and simplicity. In fact, for very small datasets, it may outperform more complex algorithms like Merge Sort or Quick Sort.
• Nearly Sorted Data: When the data is already partially sorted, Insertion Sort can quickly complete the sorting process in linear time (O(n)) with minimal shifts and comparisons.
• Real-Time Applications (Online Sorting): Insertion Sort is used in applications where new data is continuously received and needs to be inserted into an already sorted list, such as in live data streams or online sorting problems.

In these cases, Insertion Sort offers an efficient solution with less memory usage and faster sorting times for smaller or incrementally updated data.

Q. Can Insertion Sort be improved or optimized?

While the basic Insertion Sort algorithm is relatively simple and effective, there are a few optimizations that can be applied to improve its efficiency:

• Binary Insertion Sort: Instead of performing a linear search to find the correct position of an element, a binary search can be used to locate the appropriate insertion point more quickly (in O(log n) time). This reduces the number of comparisons but does not affect the shifting of elements, so the overall time complexity remains O(n²).
• Hybrid Algorithms: In practice, Insertion Sort is often combined with other sorting algorithms in hybrid approaches. For example, Timsort (used in Python’s sorting algorithm) and IntroSort (used in C++’s STL sort) use Insertion Sort for smaller subarrays during recursive sorting because of its efficiency with small datasets.

While these optimizations can make Insertion Sort more efficient in certain situations, the fundamental time complexity remains O(n²) for the worst and average cases.

Suggested Reads: 

1. Learn About Asymptotic Notations (+ Graphs & Real-Life Examples)
2. Difference Between Hashing And Encryption Decoded
3. 53 Frequently Asked Linked List Interview Questions With Answers 2024
4. Data Structure Interview Questions For 2024 [With Detailed Answers]
5. Tree Topology | Advantages & Disadvantages In Computer Network
6. Decoding Data Redundancy In DBMS| Causes, Advantages, Solutions