Sorting is one of the most important concepts in Data Structures and Algorithms (DSA). It helps organize data efficiently, making searching, processing, and analyzing information much faster.
Among the elementary sorting algorithms, Insertion Sort is one of the most efficient for small or nearly sorted datasets. It is simple to understand and is widely taught in schools, colleges, and coding interviews.
In this comprehensive guide, you’ll learn everything about Insertion Sort, including its working principle, algorithm, examples, Java implementation, time complexity, advantages, disadvantages, interview questions, and much more.
📚 Table of Contents
- What is Insertion Sort?
- Why is it called Insertion Sort?
- Real-Life Analogy
- How Insertion Sort Works
- Step-by-Step Example
- Insertion Sort Algorithm
- Flow of Insertion Sort
- Java Program
- Dry Run of the Program
- Time Complexity Analysis
- Space Complexity
- Is Insertion Sort Stable?
- Is Insertion Sort In-Place?
- Why is Insertion Sort Efficient for Nearly Sorted Arrays?
- Advantages
- Disadvantages
- Applications
- Bubble Sort vs Selection Sort vs Insertion Sort
- Frequently Asked Questions
- Conclusion
🃏 What is Insertion Sort?
Insertion Sort is a comparison-based sorting algorithm that builds the sorted array one element at a time.
Instead of repeatedly swapping adjacent elements like Bubble Sort or repeatedly selecting the smallest element like Selection Sort, Insertion Sort takes one element and inserts it into its correct position in the already sorted part of the array.
Initially, the first element is assumed to be sorted.
🤔 Why is it Called Insertion Sort?
The algorithm works by inserting each new element into its proper position among the previously sorted elements.
For example,
5 2 4 6 1 3
The algorithm:
- Inserts 2 before 5
- Inserts 4 between 2 and 5
- Inserts 6 after 5
- Inserts 1 at the beginning
- Inserts 3 between 2 and 4
Since every element is inserted into its correct position, the algorithm is called Insertion Sort.
🃏 Real-Life Analogy
Imagine you’re holding a set of playing cards.
Whenever you receive a new card:
- You don’t reshuffle all the cards.
- Instead, you insert the new card into its correct position.
Example:
You already have:
3 5 8
You receive:
4
You simply insert it between 3 and 5.
Result:
3 4 5 8
This is exactly how Insertion Sort works.
⚙️ How Insertion Sort Works
The algorithm follows these steps:
1️⃣ Assume the first element is already sorted.
2️⃣ Pick the next element (called the key).
3️⃣ Compare the key with elements on its left.
4️⃣ Shift all larger elements one position to the right.
5️⃣ Insert the key into the vacant position.
6️⃣ Repeat until all elements are sorted.
✨ Step-by-Step Example
Consider the array:
[5, 2, 4, 6, 1, 3]
Initially,
Sorted Unsorted
[5] [2,4,6,1,3]
🔹 Pass 1
Key = 2
Compare with 5.
Since 2 is smaller,
Shift 5.
5 5 4 6 1 3
Insert 2.
2 5 4 6 1 3
🔹 Pass 2
Key = 4
Compare with 5.
Shift 5.
2 5 5 6 1 3
Compare with 2.
Stop.
Insert 4.
2 4 5 6 1 3
🔹 Pass 3
Key = 6
Compare with 5.
No shifting required.
2 4 5 6 1 3
🔹 Pass 4
Key = 1
Shift 6
Shift 5
Shift 4
Shift 2
Insert 1.
1 2 4 5 6 3
🔹 Pass 5
Key = 3
Shift 6
Shift 5
Shift 4
Insert 3.
1 2 3 4 5 6
🎉 Array sorted successfully.
📝 Insertion Sort Algorithm
Step 1: Start
Step 2: Assume the first element is sorted.
Step 3: Pick the next element (key).
Step 4: Compare it with previous elements.
Step 5: Shift larger elements to the right.
Step 6: Insert the key at the correct position.
Step 7: Repeat until all elements are sorted.
Step 8: Stop.
🔄 Flow of Insertion Sort
Start
↓
Assume First Element is Sorted
↓
Pick Next Element (Key)
↓
Compare with Previous Elements
↓
Shift Larger Elements Right
↓
Insert Key
↓
Next Element
↓
Array Sorted
↓
Stop
💻 Java Program
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;
while(j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int arr[] = {5,2,4,6,1,3};
insertionSort(arr);
System.out.println("Sorted Array:");
for(int num : arr)
System.out.print(num + " ");
}
}
🖥 Output
Sorted Array
1 2 3 4 5 6
🔍 Dry Run
Input
8 4 3 7
Pass 1
Key = 4
Shift 8
Insert 4
4 8 3 7
Pass 2
Key = 3
Shift 8
Shift 4
Insert 3
3 4 8 7
Pass 3
Key = 7
Shift 8
Insert 7
3 4 7 8
🎉 Sorted.
📈 Time Complexity Analysis
🔴 Worst Case
Suppose the array is in reverse order.
5 4 3 2 1
Every new element must be compared with all previously sorted elements.
Number of comparisons:
Pass 1
1
Pass 2
2
Pass 3
3
…
Last Pass
n - 1
Total comparisons:
[
1+2+3+\cdots+(n-1)
]
Using the formula,
[
\frac{n(n-1)}{2}
]
Ignoring constants,
[
O(n^2)
]
🟢 Best Case
Suppose the array is already sorted.
1 2 3 4 5
Each key is compared only once with the previous element.
No shifting is required.
Total comparisons:
n - 1
Therefore,
[
O(n)
]
🟡 Average Case
For a randomly arranged array, each element is expected to move about halfway through the sorted portion.
Therefore,
[
O(n^2)
]
💾 Space Complexity
Insertion Sort uses only one additional variable (key) for inserting the current element.
Therefore,
Space Complexity = O(1)
📌 Is Insertion Sort Stable?
✅ Yes.
Equal elements retain their original relative order.
Example:
Before sorting
10A 20 10B
After sorting
10A 10B 20
Notice that 10A still appears before 10B.
Therefore,
Insertion Sort is a stable sorting algorithm.
📌 Is Insertion Sort In-Place?
✅ Yes.
It sorts the array within the same memory location.
No additional array is required.
🚀 Why is Insertion Sort Efficient for Nearly Sorted Arrays?
This is one of the biggest advantages of Insertion Sort.
Suppose the array is
1 2 3 5 4
Only one element (4) is out of place.
Insertion Sort only shifts 5 and inserts 4.
Very little work is performed.
This is why Insertion Sort is much faster than Bubble Sort and Selection Sort on nearly sorted data.
🌍 Applications of Insertion Sort
Insertion Sort is commonly used for:
- 🎓 Learning Data Structures and Algorithms
- 📚 Small datasets
- ⚡ Nearly sorted arrays
- 🔧 Hybrid algorithms such as Tim Sort
- 🧠 Online sorting (sorting data as it arrives)
📊 Bubble Sort vs Selection Sort vs Insertion Sort
| Feature | Bubble Sort | Selection Sort | Insertion Sort |
|---|---|---|---|
| Technique | Swap adjacent elements | Select minimum element | Insert each element into sorted portion |
| Best Case | O(n²) Normal / O(n) Optimized | O(n²) | O(n) |
| Average Case | O(n²) | O(n²) | O(n²) |
| Worst Case | O(n²) | O(n²) | O(n²) |
| Stable | ✅ Yes | ❌ No | ✅ Yes |
| In-place | ✅ Yes | ✅ Yes | ✅ Yes |
| Efficient for Nearly Sorted Data | ❌ No | ❌ No | ✅ Yes |
❓ Frequently Asked Questions (FAQs)
Q1. Why is it called Insertion Sort?
Because every new element is inserted into its correct position within the already sorted part of the array.
Q2. Is Insertion Sort stable?
Yes. Equal elements maintain their original relative order.
Q3. Is Insertion Sort an in-place algorithm?
Yes. It requires only constant extra memory.
Q4. Why is Insertion Sort faster for nearly sorted arrays?
Because only a few elements need to be shifted. If the array is almost sorted, very little work is required.
Q5. What is the best-case time complexity?
O(n)
Q6. What is the worst-case time complexity?
O(n²)
Q7. Which real-life example best explains Insertion Sort?
Arranging playing cards in your hand by inserting each new card into its correct position.
🎯 Key Takeaways
- 🃏 Insertion Sort inserts one element at a time into the sorted portion of the array.
- 📌 It assumes the first element is already sorted.
- 🔄 Larger elements are shifted to create space for the current element.
- 🚀 It performs exceptionally well on small and nearly sorted datasets.
- 📈 Best Case = O(n)
- 📈 Average Case = O(n²)
- 📈 Worst Case = O(n²)
- 💾 Space Complexity = O(1)
- ✅ It is stable and in-place.
🎉 Conclusion
Insertion Sort is one of the most practical elementary sorting algorithms. While its worst-case time complexity is O(n²), its excellent performance on small and nearly sorted datasets makes it highly valuable. In fact, many advanced sorting algorithms, such as Tim Sort, use Insertion Sort internally for sorting small partitions because of its low overhead and simplicity.
For beginners, mastering Insertion Sort is an important milestone in learning DSA. It introduces concepts like shifting elements, maintaining a sorted portion, and analyzing algorithm efficiency. Once you understand Insertion Sort thoroughly, you’ll find it much easier to learn advanced algorithms like Merge Sort, Quick Sort, and Heap Sort.
