Introduction to Insertion Sort Algorithm

Think about students lining up by height: each new student arrives, looks for their correct position in the line, shifting a few others if needed. Or consider browser bookmarks; when you save a new one, the browser doesn’t rearrange everything from scratch. Instead, it simply places the bookmark at its proper spot. All the above examples use Insertion Sort. There are so many other scenarios where we apply the insertion sort algorithm without realizing it. In this blog, we will explore insertion sort step by step, its working, pseudocode, code implementation, complexity, and real-world applications, other than the sorting of playing cards.

Table of Contents:

• What are Sorting Algorithms?
• What is Insertion Sort?
• How does Insertion Sort Work?
• Code Implementation of Insertion Sort
• Dry Run of the Code
• Edge cases of Insertion Sort
• Complexity Analysis of Insertion Sort in Data Structures
• Complexity Comparison with Other Sorting Algorithms
• Applications of Insertion Sort
• Advantages of Insertion Sort in Data Structures
• Disadvantages of Insertion Sort in Data Structures
• Conclusion

What are Sorting Algorithms?

The algorithms used to arrange data into a specific order are called sorting algorithms. You can choose any order, either ascending or descending, and use them to sort any data structure. It could be numbers, characters, alphabets, dates, etc. Computers apply sorting algorithms everywhere, from organizing files in your folder to displaying emails by date to arranging scores on a leaderboard. 

There are many sorting algorithms developed, but the insertion sort algorithm is one of the simplest sorting algorithms. It also very closely reflects the way we naturally organize things, so for complete beginners to computer science and data structures, it is not too daunting. It provides a solid foundation for understanding more advanced sorting algorithms.

What is Insertion Sort?

Insertion sort is a simple sorting algorithm that builds the final sorted list one element at a time in the same array. When your input array is sorted in the given array itself, it is called in-place sorting. Instead of trying to sort everything at once, this sorting technique takes each new element and places it into its correct position among the already sorted elements.

How does Insertion Sort Work?

In this sorting algorithm, it starts with the first element, which we consider “already sorted by itself”. Then it considers the next element and inserts it into its proper place among the elements before it. This process repeats until the entire list is ordered. Let us look at this process step by step, with the help of a simple array, [5, 3, 4, 1].

Step 1: Start with the First Element

A single element is always “sorted.” Hence, we will consider this single-element array as our sorted part of the array and the rest of the array as the unsorted part of the array. 

Step 2: Take the Next Element

Now, we will move on to the next element, which is 3 here. Our goal is to place it in its “correct position” in the sorted part of the array. So we will compare it with the elements of the sorted part of the array. Since 3 < 5, insert it before 5.

Step 3: Continue This Process Until the End

• Step 2 will continue until there is no element left in the unsorted part of the array. We will now take the next element, 4. 
• First, we will compare it with 5, since 4 < 5, 4 will come before 5. 
• Then we will compare with 3. Since 4 > 3, insert 4 after 3.

Step 4: Last Element

For the last element as well, we have to insert it into the sorted part. We will compare it with every element and insert it in its right place. In this example, it will come before 3.

Now that we are not left with any unsorted part of the array, we will stop. This is our final sorted array. 

Pseudocode of the Insertion Sort Algorithm

Pseudocode is written to implement the logic in a way that can be used to implement the complete code. Here, we will run a for loop starting from the second element (index 1), because the first element alone can be considered already sorted.

At each step, the array is divided conceptually into two parts:

• Sorted part: the elements from index 0 to i-1, which are already arranged in order.
• Unsorted part: the remaining elements from index i to the end of the array.

The algorithm picks the first element from the unsorted part (the key) and compares it with elements in the sorted part. 

If the key is smaller, elements in the sorted part are shifted one position to the right until the correct position for the key is found. 

Finally, the key is inserted into that position, extending the sorted part by one element. This process repeats until the entire array becomes sorted.

procedure insertionSort(A):
    n = length(A)
    for i from 1 to n-1:
        key = A[i]          
        j = i - 1
        // Shift elements of A[0..i-1], that are greater than key,
        // to one position ahead of their current position
        while j >= 0 and A[j] > key:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = key

Code Implementation of Insertion Sort

Let us now implement the code with the help of the pseudocode in C++, Java as well and Python.

Insertion Sort in CPP

Code:

Output:

Insertion Sort in Python

Output:

Insertion Sort in Java

Code:

Output:

Dry Run of the Code

For beginners, nested loops can be hard to visualize and understand. Let’s take an example and walk through each pass, tracking the loop variables (i, j, and key) and the array state so you fully grasp the concept. We will take the example of 

We will run the for loop from i = 1 to i = n-1. Each value of i will be considered as a pass. 

For each i, j will take values starting from i-1 and move backwards (decreasing one by one) as long as the elements on the left are greater than the current key. 

Once a smaller element is found, or j becomes -1, the loop stops, and the key is inserted at the correct position.

Edge cases of Insertion Sort

After the above explanation, the insertion sort algorithm should be clear to you. But the inputs are usually not this straightforward. There are some special cases that you must be aware of while writing code. These special situations are called edge cases. Let’s look at a few edge cases to understand how the algorithm behaves:

1. Already Sorted Array
   • Example: [1, 2, 3, 4, 5]
   • Each new key will always be greater than the elements before it, so no shifting happens. This is called the best-case scenario since we need to do n-1 comparisons, which makes it very fast.
2. Reverse Sorted Array
   • Example: [5, 4, 3, 2, 1]
   • Every key is smaller than all elements before it, so at each pass, the entire sorted part is shifted. This is the worst-case scenario because we are making maximum comparisons and shifts.
3. Array with All Equal Elements
   • Example: [2, 2, 2, 2, 2]
   • The key is always equal to the previous elements, so the inner loop exits immediately. It is minimal work, but still performs the for loop.
4. Array with One Element or Empty Array
   • Example: [7] or [ ]
   • In such cases, no passes are needed, as the array is already fundamentally sorted.

Complexity Analysis of Insertion Sort in Data Structures

Whenever developers design an algorithm, their goal is to make it as efficient and fast as possible. To evaluate this efficiency, we perform a process called complexity analysis. Instead of looking at individual iterations, we analyze how the algorithm behaves as the input size grows. The three main metrics we use for this evaluation are time complexity, space complexity, and stability. Let us look at them one by one for the insertion sort algorithm.

Time Complexity

Time complexity tells us how the number of operations grows with the size of the input. It measures the effect of input size on the running time of the algorithm.

• Best-case scenario: When the elements are already sorted, no shifting is needed. We simply traverse the collection once to verify order.
  Time Complexity: O(n)
• Worst-case scenario: When the elements are sorted in reverse order, every new element must be compared with all the previous ones and shifted to the beginning.
  Time Complexity: O(n²)
• Average case scenario: When elements are in random order, each new element is compared with about half of the sorted part on average.
  Time Complexity: O(n²)

Space Complexity

Insertion sort is an in-place sorting algorithm. It does not require extra data structures for processing, except for a temporary variable (key) used during comparisons.

Space Complexity: O(1)

Stability of the algorithm

The insertion sort algorithm is a stable algorithm, which means that if two elements are equal, their relative order in the original array is preserved in the sorted array. This property is particularly useful when sorting records with multiple fields.

Complexity Comparison with Other Sorting Algorithms

Even though bubble sort and the insertion sort have the same time complexity, the insertion sort algorithm is preferred because it is faster in practice. It is also always preferred with a small-sized dataset.

Applications of Insertion Sort

Here are some of the common uses of the insertion sort algorithm in your daily life scenarios and computer scenarios.

• Managing Browser Bookmarks: When a new bookmark is added, it is inserted into the correct alphabetical or category position instead of re-sorting the entire list.
• Email Clients Sorting by Date or Priority: New emails are slotted into the right spot in an already sorted inbox, maintaining order without a full re-sort.
• Leaderboard Updates in Games or Online Platforms: A new score is inserted at its proper rank, pushing others down, just like insertion sort.
• Spreadsheets and Databases: When rows or records are added to a sorted dataset, the insertion sort algorithm ensures they are placed in the correct order efficiently.
• Hybrid Sorting Algorithms: Many high-performance algorithms (like Python’s Timsort and C++’s IntroSort) switch to insertion sort for small subarrays because it’s faster in those cases.

Even though the insertion sort algorithm does not work well with large datasets, it is still used in the tools we rely on daily.  

Advantages of Insertion Sort in Data Structures

• Insertion sort is simple to implement, making it easy for beginners to understand and work with.
• It is an in-place algorithm, which means it requires only O(1) extra memory.
• Being a stable sorting algorithm, it maintains the relative order of equal elements in the input.
• It is efficient for small datasets, often performing better than more complex algorithms in such cases.
• The algorithm is also adaptive, meaning it runs very fast on nearly sorted or partially sorted data.

Disadvantages of Insertion Sort in Data Structures

• Insertion sort becomes inefficient for large datasets because it has O(n²) time complexity in both the average and worst cases.
• It is not suitable for parallelization, as the algorithm is inherently sequential in nature. Parallelization means breaking a task into smaller parts and running them at the same time on multiple processors to finish faster.
• In addition, it requires more shifts compared to other algorithms, especially when dealing with reverse-sorted data.

Conclusion

Insertion sort is one of the foundational sorting algorithms. Mastering it will help you understand other complex sorting algorithms in data structures better. It might not be the fastest algorithm for large datasets, but it is a good starting point since it closely mirrors the way we naturally organize items in real life, making it intuitive to understand. It also plays an important role in hybrid algorithms like Timsort, proving its relevance even today. 

To learn more about other data structure algorithms, explore the additional useful resources.

Useful resources

• Sorting in Data Structure: Definition, Types, Applications
• What is Selection Sort Algorithm in Data Structures?
• Quick Sort Algorithm: A Comprehensive Guide
• Sorting in Data Structure: Definition, Types, Applications
• Sorting Algorithms in C++

Insertion Sort Algorithm – FAQs