Insertion Sort in Design and Analysis of Algorithms (DAA)
Learning Objectives
After completing this tutorial, students will be able to:
- Understand the concept of Insertion Sort.
- Explain the working principle of Insertion Sort.
- Write the algorithm and pseudocode of Insertion Sort.
- Perform a complete dry run of Insertion Sort.
- Implement Insertion Sort in C, C++, Java and Python.
- Analyze Best, Average and Worst Case complexities.
- Compare Insertion Sort with Bubble Sort and Merge Sort.
- Prepare for AKTU examinations, viva and placement interviews.
Introduction
Sorting is one of the most fundamental operations in Computer Science. Many applications such as arranging examination results, maintaining customer records, organizing product lists and database indexing rely on efficient sorting techniques. Insertion Sort is one of the simplest sorting algorithms. Instead of repeatedly swapping adjacent elements, it maintains a sorted portion of the array and inserts each new element into its correct position. Initially, the first element is considered sorted. The remaining elements are processed one by one until the entire array becomes sorted.
Definition of Insertion Sort
Insertion Sort is a stable, comparison-based and in-place sorting algorithm that builds the sorted array gradually by inserting each element into its proper position within the already sorted portion.
Why is it Called Insertion Sort?
The algorithm is called Insertion Sort because each new element is inserted into its correct position within the sorted part of the array, just as a player inserts a new card into the proper position in a hand of playing cards.
Working Principle of Insertion Sort
Insertion Sort follows the following steps:
- Assume the first element is already sorted.
- Select the next element (called the Key).
- Compare the key with elements in the sorted portion.
- Shift larger elements one position to the right.
- Insert the key into its correct position.
- Repeat the process until all elements are sorted.
Characteristics of Insertion Sort
| Property | Description |
|---|---|
| Sorting Technique | Comparison Based |
| Sorting Method | In-place Sorting |
| Stable | Yes |
| Adaptive | Yes |
| Extra Memory | O(1) |
| Method | Insertion by Shifting Elements |
| Suitable For | Small and Nearly Sorted Datasets |
Need of Insertion Sort
Insertion Sort is still widely used despite the availability of faster sorting algorithms because it performs efficiently on small datasets and nearly sorted arrays. It also helps students understand several important programming concepts.
- Insertion of elements into a sorted sequence.
- Shifting array elements.
- Comparison-based sorting.
- Loop implementation.
- Adaptive sorting.
- Foundation for advanced sorting techniques.
Insertion Sort Algorithm
InsertionSort(A, n)
for(i = 1; i < n; i++)
{
key = A[i];
j = i - 1;
while(j >= 0 && A[j] > key)
{
A[j + 1] = A[j];
j--;
}
A[j + 1] = key;
}
Pseudocode
START
FOR i = 1 TO n - 1
key = A[i]
j = i - 1
WHILE j >= 0 AND A[j] > key
A[j + 1] = A[j]
j = j - 1
END WHILE
A[j + 1] = key
END FOR
STOP
Flowchart of Insertion Sort
The following flowchart illustrates the complete execution process of Insertion Sort.
Basic Example
Consider the following unsorted array.
64 25 12 22 11
Initially, only the first element (64) is considered sorted. The second element (25) is selected as the key and inserted before 64. Similarly, each remaining element is inserted into its correct position, gradually expanding the sorted portion until the complete array becomes sorted.
Dry Run of Insertion Sort
Consider the following unsorted array:
64 25 12 22 11
Insertion Sort considers the first element as already sorted. During each iteration, the next element (called the Key) is inserted into its correct position within the sorted portion of the array.
Pass 1 (Key = 25)
Initially,
[64] 25 12 22 11
- Sorted Portion : 64
- Key = 25
- Compare 25 with 64
- Shift 64 one position to the right
- Insert 25 at the beginning
25 64 12 22 11
Pass 2 (Key = 12)
Sorted Portion:
25 64 12 22 11
- Key = 12
- Shift 64
- Shift 25
- Insert 12 at the beginning
12 25 64 22 11
Pass 3 (Key = 22)
Sorted Portion:
12 25 64 22 11
- Key = 22
- Shift 64
- Shift 25
- Insert 22 after 12
12 22 25 64 11
Pass 4 (Key = 11)
Sorted Portion:
12 22 25 64 11
- Key = 11
- Shift 64
- Shift 25
- Shift 22
- Shift 12
- Insert 11 at the beginning
11 12 22 25 64
The array is now completely sorted.
Summary of All Passes
| Iteration | Sorted Portion After Insertion |
|---|---|
| Initial | 64 25 12 22 11 |
| Pass 1 | 25 64 12 22 11 |
| Pass 2 | 12 25 64 22 11 |
| Pass 3 | 12 22 25 64 11 |
| Pass 4 | 11 12 22 25 64 |
Insertion Sort Visualization
The following illustration shows how each key element is inserted into its correct position while the sorted portion of the array gradually increases.
C Program for Insertion Sort
#include
int main()
{
int a[]={64,25,12,22,11};
int n=5;
for(int i=1;i=0 && a[j]>key)
{
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
printf("Sorted Array:\n");
for(int i=0;i C++ Program for Insertion Sort
#include
using namespace std;
int main()
{
int a[]={64,25,12,22,11};
int n=5;
for(int i=1;i=0 && a[j]>key)
{
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
for(int i=0;i Java Program for Insertion Sort
public class InsertionSort
{
public static void main(String args[])
{
int a[]={64,25,12,22,11};
for(int i=1;i=0 && a[j]>key)
{
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
for(int x:a)
System.out.print(x+" ");
}
}
Python Program for Insertion Sort
a=[64,25,12,22,11]
for i in range(1,len(a)):
key=a[i]
j=i-1
while j>=0 and a[j]>key:
a[j+1]=a[j]
j=j-1
a[j+1]=key
print("Sorted Array")
print(a)
Time Complexity Analysis of Insertion Sort
The performance of Insertion Sort depends on the initial arrangement of the input elements. Since the algorithm inserts each key element into its correct position by shifting larger elements, its running time varies according to the number of comparisons and shifts required.
| Case | Time Complexity | Description |
|---|---|---|
| Best Case | O(n) | Array is already sorted. |
| Average Case | O(n2) | Array elements are randomly arranged. |
| Worst Case | O(n2) | Array is sorted in reverse order. |
Best Case Time Complexity
The best case occurs when the array is already sorted. In this situation, every key element is already in its correct position, so no shifting is required. Only one comparison is performed for each element. Therefore, the Best Case Time Complexity is:
O(n)
Average Case Time Complexity
When the input array is randomly arranged, each key element must be compared with several previously sorted elements before it reaches its correct position. Consequently, the average number of comparisons and shifts is approximately n²/4. Hence,
O(n2)
Worst Case Time Complexity
The worst case occurs when the array is arranged in descending order and needs to be sorted in ascending order. Every key element must be shifted through the entire sorted portion, resulting in the maximum number of comparisons and shifts. Therefore,
Worst Case = O(n2)
Space Complexity
Insertion Sort performs sorting within the original array and requires only one additional variable to store the key element. Therefore,
Space Complexity = O(1)
Since no additional array is required, Insertion Sort is classified as an In-place Sorting Algorithm.
Number of Comparisons
The number of comparisons depends on the arrangement of the input array.
| Case | Comparisons |
|---|---|
| Best Case | n − 1 |
| Average Case | Approximately n²/4 |
| Worst Case | n(n−1)/2 |
Number of Shifts
Unlike Bubble Sort, Insertion Sort mainly performs shifting instead of frequent swapping. The number of shifts depends on how far the key element must move towards the beginning of the array.
| Case | Shifts |
|---|---|
| Best Case | 0 |
| Average Case | Approximately n²/4 |
| Worst Case | n(n−1)/2 |
Advantages of Insertion Sort
- Simple and easy to implement.
- Stable sorting algorithm.
- Adaptive in nature.
- Excellent for nearly sorted arrays.
- Requires only constant extra memory.
- Efficient for small datasets.
- Performs fewer operations than Bubble Sort on nearly sorted data.
Disadvantages of Insertion Sort
- Not suitable for large datasets.
- Worst Case Time Complexity is O(n²).
- Large number of shifts may be required.
- Slower than Merge Sort, Heap Sort and Quick Sort for large inputs.
Applications of Insertion Sort
Insertion Sort is widely used in situations where the input size is small or the data is already nearly sorted.
- Sorting small datasets.
- Nearly sorted arrays.
- Hybrid sorting algorithms.
- Database indexing.
- Online sorting.
- Educational purposes.
- Interview preparation.
Insertion Sort vs Bubble Sort
| Feature | Insertion Sort | Bubble Sort |
|---|---|---|
| Technique | Insertion by Shifting | Adjacent Swapping |
| Stable | Yes | Yes |
| Adaptive | Yes | Yes (Optimized) |
| Best Case | O(n) | O(n) |
| Worst Case | O(n²) | O(n²) |
| Performance on Nearly Sorted Data | Excellent | Good |
| Number of Swaps | Very Few | Many |
Insertion Sort vs Merge Sort
| Feature | Insertion Sort | Merge Sort |
|---|---|---|
| Technique | Insertion | Divide and Conquer |
| Best Case | O(n) | O(n log n) |
| Worst Case | O(n²) | O(n log n) |
| Space Complexity | O(1) | O(n) |
| Stable | Yes | Yes |
| Suitable For | Small Arrays | Large Arrays |
Complexity Summary
| Property | Value |
|---|---|
| Best Case Time | O(n) |
| Average Case Time | O(n²) |
| Worst Case Time | O(n²) |
| Space Complexity | O(1) |
| Stable | Yes |
| Adaptive | Yes |
| In-place | Yes |
| Recursive | No |
Solved Example
Sort the following array in ascending order using Insertion Sort.
35 20 15 40 10
Solution
| Pass | Array After Insertion |
|---|---|
| Initial | 35 20 15 40 10 |
| Pass 1 (Key = 20) | 20 35 15 40 10 |
| Pass 2 (Key = 15) | 15 20 35 40 10 |
| Pass 3 (Key = 40) | 15 20 35 40 10 |
| Pass 4 (Key = 10) | 10 15 20 35 40 |
Hence, the sorted array is:
10 15 20 35 40
AKTU Previous Year Questions
- Explain Insertion Sort with a suitable example.
- Write the algorithm and pseudocode of Insertion Sort.
- Analyze the Best, Average and Worst Case Time Complexity of Insertion Sort.
- Differentiate between Insertion Sort and Bubble Sort.
- Why is Insertion Sort called a stable sorting algorithm?
- Explain the shifting process in Insertion Sort.
- Perform Insertion Sort on a given array and show each iteration.
Viva Questions
- What is Insertion Sort?
- Why is it called Insertion Sort?
- What is the key element in Insertion Sort?
- Why is the first element considered sorted?
- Is Insertion Sort stable?
- Is Insertion Sort adaptive?
- What is the Best Case Time Complexity?
- What is the Worst Case Time Complexity?
- What is the Space Complexity of Insertion Sort?
- Which operation is mainly performed in Insertion Sort: shifting or swapping?
Interview Questions
- Why is Insertion Sort efficient for nearly sorted arrays?
- What is the difference between shifting and swapping?
- How is Insertion Sort different from Bubble Sort?
- Why is Insertion Sort considered adaptive?
- Can Insertion Sort be used for linked lists?
- Differentiate Insertion Sort and Merge Sort.
- Differentiate Insertion Sort and Selection Sort.
- What are the practical applications of Insertion Sort?
- Why is Insertion Sort an in-place sorting algorithm?
- Can Insertion Sort be implemented recursively?
Multiple Choice Questions (MCQs)
| Question | Answer |
|---|---|
| 1. Insertion Sort inserts one ______ during each iteration. | Key Element |
| 2. Insertion Sort is a ______ sorting algorithm. | Stable |
| 3. Best Case Time Complexity is ______. | O(n) |
| 4. Space Complexity is ______. | O(1) |
| 5. Insertion Sort is a ______ sorting algorithm. | In-place |
| 6. Insertion Sort mainly performs ______. | Shifting |
| 7. The first element is initially considered ______. | Sorted |
| 8. Worst Case Time Complexity is ______. | O(n²) |
| 9. Insertion Sort performs efficiently on ______ arrays. | Nearly Sorted |
| 10. Insertion Sort is based on ______. | Comparison |
Practice Questions
- Sort the array 60, 25, 45, 15, 30 using Insertion Sort.
- Explain Insertion Sort with a neat diagram.
- Write C, C++, Java and Python programs for Insertion Sort.
- Compare Insertion Sort with Bubble Sort.
- Compare Insertion Sort with Merge Sort.
- Explain why Insertion Sort is adaptive.
- Find the total number of comparisons in the worst case for an array of 7 elements.
- Discuss the advantages and disadvantages of Insertion Sort.
Key Takeaways
- Insertion Sort builds the sorted array one element at a time.
- Each iteration inserts one key element into its correct position.
- The algorithm mainly performs shifting rather than repeated swapping.
- Insertion Sort is stable, adaptive and in-place.
- Its Best Case Time Complexity is O(n).
- It performs very well for small and nearly sorted datasets.
Summary
Insertion Sort is one of the simplest and most efficient sorting algorithms for small datasets and nearly sorted arrays. It builds the sorted portion of the array gradually by selecting one key element at a time and inserting it into its correct position. Although the Worst Case Time Complexity of Insertion Sort is O(n2), its adaptive nature and low memory requirements make it useful in many practical applications and hybrid sorting algorithms. Understanding Insertion Sort helps students learn the concepts of comparison, shifting, insertion and algorithm analysis. It also provides a strong foundation for studying advanced sorting techniques such as Merge Sort, Quick Sort and Heap Sort.