Insertion sort builds the sorted array one element at a time. It takes the next unsorted element, then slides it left through the already-sorted portion until it reaches the right spot. It is inefficient on large lists but fast in practice on nearly-sorted data, and it is the algorithm most people intuitively use when sorting a hand of cards.
Example: Sort 5 numbers in ascending order.
When to use this
→Nearly-sorted arrays — runs in O(n) when data is almost in order
→Online sorting — can sort a stream of incoming elements one at a time
→Small arrays (n < ~20) — often faster than O(n log n) sorts due to low overhead
→Used as the base case in hybrid sorts like Timsort and Introsort
Insertion sort treats the first element as a sorted list of one. It then takes each remaining element and slides it left into its correct position in the sorted prefix.
Space play/pause← → stepR replay+ − speed
active line highlighted
1
definsertion_sort(arr):
2
foriinrange(1,len(arr)):
3
key=arr[i]
4
j=i-1
5
whilej>=0andarr[j]>key:
6
arr[j+1]=arr[j]
7
j-=1
8
arr[j+1]=key
Quick check
When does insertion sort perform best?
What happens to the elements that are larger than the key being inserted?