Visualizer › Sorting
Insertion Sort
Builds a sorted part on the left and inserts each next element into its correct place, like sorting playing cards in your hand.
How it works
- Very fast on small or nearly sorted arrays.
- Stable and in-place.
- Used inside faster sorts (e.g. Timsort) for small pieces.
Complexity
- Best time: O(n)
- Average time: O(n²)
- Worst time: O(n²)
- Extra space: O(1)
- Stable: yes
Code (Python)
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j] # shift right
j -= 1
a[j + 1] = key
return aPractise: Arrays problems