What is the best-case complexity of Insertion Sort?
Updated Apr 28, 2026
Short answer
The best-case time complexity of Insertion Sort is O(n) when the input array is already sorted. In this case, each element only needs to be compared once with the previous element and no shifting is required. Insertion Sort is efficient for small or nearly sorted datasets because it can take advantage of existing order.
Deep explanation
Insertion Sort works by dividing an array into two parts:
- A sorted portion on the left.
- An unsorted portion on the right.
It takes elements from the unsorted portion one by one and inserts them into their correct position in the sorted portion.
Example:
Array:
[1, 2, 3, 4, 5]This array is already sorted.
Insertion Sort checks each element:
Compare 2 with 1 → already in correct positionCompare 3 with 2 → already in correct positionCompare 4 with 3 → already in correct positionCompare 5 with 4 → already in correct positionNo shifting or swapping is needed.
---
Why the Best Case Is O(n)
Insertion Sort normally performs two actions:
- Comparison
- Checks whether the current element is smaller than elements before it.
- Shifting
- Moves larger elements to make space for insertion.
In the best case, when the array is already sorted:
[1, 2, 3, 4, 5]For every element:
- It compares once with the previous element.
- It finds the correct position immediately.
- It performs no shifts.
The algorithm makes approximately n - 1 comparisons:
1 comparison + 1 comparison + ... + 1 comparison
= O(n)---
Insertion Sort Example
def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1
while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1
arr[j + 1] = keyFor a sorted array:
arr = [1, 2, 3, 4, 5]
insertion_sort(arr)The while loop condition fails immediately for every element because no element needs to move.
---
Complexity Analysis of Insertion Sort
| Case | Time Complexity | Explanation |
|---|---|---|
| Best Case | O(n) | Array is already sorted |
| Average Case | O(n²) | Elements are randomly ordered |
| Worst Case | O(n²) | Array is sorted in reverse order |
| Space Complexity | O(1) | Sorts in-place |
---
Worst Case Comparison
Consider a reverse-sorted array:
[5, 4, 3, 2, 1]Each new element must be moved to the beginning:
5↓4 5↓3 4 5↓2 3 4 5↓1 2 3 4 5This requires many comparisons and shifts:
1 + 2 + 3 + ... + (n-1)
= O(n²)---
Why Insertion Sort Is Useful
Although its average and worst-case performance are O(n²), Insertion Sort is still useful because:
- It is simple to implement.
- It uses very little extra memory.
- It performs well on nearly sorted data.
- It is efficient for small input sizes.
- It is stable, meaning equal elements maintain their original order.
Many advanced sorting algorithms use Insertion Sort internally for small subarrays because of its low overhead.
Real-world example
Imagine sorting playing cards in your hand.
If you receive cards that are already mostly arranged, you only need to insert a new card near its correct position.
Example:
Current hand:
[2, 5, 8, 10]
New card: 9
Insert 9:
[2, 5, 8, 9, 10]If the cards are already sorted, each new card requires only one comparison, similar to the best-case behavior of Insertion Sort.
Common mistakes
- * Assuming Insertion Sort always has `O(n²)` complexity.
- * Forgetting that the best case occurs when the array is already sorted.
- * Confusing best-case complexity with average-case complexity.
- * Ignoring that shifting operations cause the worst-case `O(n²)` behavior.
- * Thinking Insertion Sort is always better than faster algorithms like Merge Sort or Quick Sort.
- * Forgetting that Insertion Sort is efficient for nearly sorted data.
Follow-up questions
- Why is the best-case complexity of Insertion Sort O(n)?
- What is the worst-case complexity of Insertion Sort?
- Why is Insertion Sort good for nearly sorted arrays?
- Is Insertion Sort an in-place algorithm?
- How does Insertion Sort compare with Selection Sort?