Sorting is fundamental to computer science. Whether you are sorting numbers, names, or database records, sorting algorithms are key. One of the simplest and most commonly taught algorithms is insertion sort.
Table Of Content
- What is the Insertion Sorting Algorithm?
- Time Complexity of Insertion Sort
- ✅ Best Case Time Complexity of Insertion Sort: O(n)
- ⚠️ Worst Case Time Complexity of Insertion Sort: O(n²)
- ⚖️ Average Case Time Complexity of Insertion Sort: O(n²)
- 📌 Summary Table: Insertion Sort Time Complexity
- Space Complexity of Insertion Sort
- Insertion Sort Algorithm (Code Examples)
- Python Implementation
- Java Implementation
- Real-Life Analogy of Insertion Sorting Algorithm
- Insertion Sort vs Other Sorting Algorithms
- Applications of Insertion Sorting Algorithm
- Final Thoughts
- Related Links
But in interviews or exams, or in real life, one question always comes up:
👉 What is insertion sort time complexity?
In this article, we’ll discuss the best case, worst case, average case, and space complexity — and include examples, code snippets, and comparisons. By the end of this article, you’ll know where insertion sort is good and bad.
What is the Insertion Sorting Algorithm?
The insertion sorting algorithm is similar to sorting a hand of cards. You have sorted cards and take the next card and insert it into the sorted cards into its proper position.
The steps are:
- Start with the second element in the array.
- Compare it with all the elements before it.
- Insert it into its proper position.
- Repeat this process until all elements are sorted.
👉 This is why insertion sort is one of the most straightforward sorting methods.
Time Complexity of Insertion Sort
When considering the time complexity of insertion sort we will look at:
- Best Case (sorted array)
- Worst Case (reverse sorted array)
- Average Case (random order)
Let’s take a closer look.
✅ Best Case Time Complexity of Insertion Sort: O(n)
- If the array is already sorted, insertion sort only compares each element once.
- No shifting is required, just a linear scan.
👉 Example: [1, 2, 3, 4, 5]
Comparisons = n-1 → O(n)
⚠️ Worst Case Time Complexity of Insertion Sort: O(n²)
- If the array is sorted in reverse order, each new element must be compared with all previous elements.
- This leads to maximum shifting.
👉 Example: [5, 4, 3, 2, 1]
Comparisons ≈ (n*(n-1))/2 → O(n²)
⚖️ Average Case Time Complexity of Insertion Sort: O(n²)
- For a random array, on average, each element will be compared with half of the already sorted part.
- So total comparisons ≈ n²/4 → O(n²)
📌 Summary Table: Insertion Sort Time Complexity
|
Case |
Time Complexity |
|
Best Case |
O(n) |
|
Worst Case |
O(n²) |
| Average Case |
O(n²) |
Space Complexity of Insertion Sort
One big advantage of insertion sort is its space efficiency.
- Space Complexity: O(1)
- Only a constant amount of extra memory is required for swapping.
- This makes it an in-place sorting algorithm.
Insertion Sort Algorithm (Code Examples)
Python Implementation
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr
print(insertion_sort([5, 2, 9, 1, 5, 6]))
Java Implementation
public class InsertionSort {
public static void insertionSort(int arr[]) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j = j - 1;
}
arr[j+1] = key;
}
}
public static void main(String args[]) {
int arr[] = {5, 2, 9, 1, 5, 6};
insertionSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
Real-Life Analogy of Insertion Sorting Algorithm
Think of inserting cards into your hand:
- You take a card one at a time.
- You place it in the right order.
- You keep doing that until there are no more cards to place in your hand.
That is how insertion sort works—easy for a human to comprehend but not fast.
Insertion Sort vs Other Sorting Algorithms
📊 Comparison Table
| Algorithm | Best Case | Average Case | Worst Case | Space Complexity |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
👉 Key Takeaway:
- Insertion sort is useful for small datasets and arrays that are almost sorted.
- For large datasets algorithms like Merge Sort or Quick Sort should be used.
Applications of Insertion Sorting Algorithm
- Sorting small playing cards or small arrays in embedded systems.
- Used in hybrid sorting algorithms (e.g., Timsort in Python, which uses insertion sort for small partitions).
- Excellent for cases when, the data is already partially sorted.
Final Thoughts
The insertion sorting algorithm is incredibly simple but powerful for its intended purpose. Insertion sort’s time complexity varies as follows:
- O(n) for the best case,
- O(n²) for average and worst case.
It is not the best algorithm for processing large data sets, but for small arrays, that are almost sorted, it is hard to beat.
👉 Understanding insertion sort’s time complexity is not just about memorizing big-O values, it is also about knowing where and when it is acceptable to use insertion sort.
if you are studying for coding interviews or an exam on algorithms, you should know that insertion sort is one of the best algorithm to start with.
Related Links
