Insertion Sort
DSA · Sorting Algorithms
Theory
Insertion sort builds the sorted list one element at a time, like sorting playing cards in your hand. Each new element is shifted left past larger elements until it reaches its correct place. It runs in O(n) on nearly sorted data and O(n²) in the worst case, and it is stable and in place.
Why we use it
It is very fast for small or almost-sorted inputs, which is why real sort implementations (like Timsort) use it for small runs.
When to use it
Use it for small arrays, nearly sorted data, or when items arrive one by one and must stay sorted.
How it works
- Start: i = 1
- key = arr[i], j = i - 1
- j >= 0 and arr[j] > key? Yes: Shift arr[j] right, j = j - 1, check again. No: Place key at arr[j+1].
- i < n - 1? Yes: i = i + 1, repeat. No: Array is sorted.
- Done
Syntax
for i in 1..n-1:
key = arr[i]; j = i-1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1
arr[j+1] = key
Time: O(n²) worst, O(n) best Space: O(1) StableExample
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
print("Inserted", key, "->", arr)
return arr
insertion_sort([12, 11, 13, 5, 6])Key points
- Great for nearly sorted data
- Stable and in place
- Used inside Timsort for small runs
- O(n²) in the worst case