Insertion Sort Algorithm: Implementation, Complexity O(n²), Adaptive, and Stable (2026)
Insertion Sort builds the final sorted array one element at a time. It picks each element from the unsorted portion and inserts it into its correct position in the sorted portion, shifting greater elements to the right. This is the same strategy people use when sorting playing cards in their hands.
This tutorial covers the algorithm, step-by-step example, complexity analysis, and why Insertion Sort is both adaptive and stable — making it ideal for small or nearly-sorted datasets.
Algorithm and Complexity Analysis
The algorithm starts with index 1 (the second element) as the "key". It compares the key with elements in the sorted portion (left side) and shifts each element one position to the right until the correct insertion point is found. The key is then placed at that position. The algorithm repeats for each element from index 1 to n-1.
Worst-case and average-case time complexity is O(n²) — when the array is reverse-sorted, each key must be compared with all previous elements. Best case is O(n) when the array is already sorted (the inner while loop never executes). Space complexity is O(1). Insertion Sort is stable because elements are shifted, not swapped, preserving relative order of equal keys.
// C++
void insertionSort(int arr[], int n) {
for(int i=1; i= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
// Java
void insertionSort(int[] arr) {
for(int i=1; i= 0 && arr[j] > key) {
arr[j+1] = arr[j]; j--;
}
arr[j+1] = key;
}
}
// Python
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] = key Adaptive Property and Use Cases
Insertion Sort is adaptive — it takes advantage of existing order in the input. The more sorted the data, the fewer comparisons and shifts are needed. For an array that is already sorted, the inner while loop never executes, resulting in O(n) time. This property makes Insertion Sort ideal for hybrid algorithms like Timsort, which uses Insertion Sort for small chunks of data.
Its stability and low overhead make it the sorting algorithm of choice for small arrays (typically n < 50) in practice. It is also efficient for data that is continuously added to a sorted list — you can insert each new element in O(n) time.
// C++ — nearly sorted array runs fast
// Best case: [1, 2, 3, 4, 5] -> O(n)
// Java — used internally in Timsort
// Arrays.sort(Object[]) uses Timsort
// Python — used in sorted() and list.sort()
arr = [1, 2, 3, 4, 5]
insertion_sort(arr) # O(n)
# Nearly sorted: [1, 2, 6, 4, 5]
# Only 6 is shifted -> ~O(n)Frequently Asked Questions
What makes Insertion Sort adaptive?
Its inner loop runs fewer iterations when the input is already partially sorted. If every element is already in correct position, it runs in O(n) time.
When should I use Insertion Sort?
Use it for small datasets (n < 50), nearly-sorted data, or when elements arrive online (one at a time) and must be inserted into a sorted list.
Originally published on Ayodhyyya. Last updated June 1, 2026.