Insertion Sort in Python
Insertion sort grows a sorted prefix one value at a time and performs well on small or nearly sorted inputs.
What is Insertion Sort?
Insertion sort grows a sorted prefix one value at a time and performs well on small or nearly sorted inputs.
Sort a Python list by inserting each value into its correct position.
When should you use it?
- Practice problem solving and data structures.
- Process data when every algorithm step must be explicit.
- Prepare for programming exercises, exams, and interviews.
Insertion Sort in Python visualizer
O(n²)Use Play or Step to follow each comparison and data movement.
Example code
main.py
def insertion_sort(values):
result = values.copy()
for index in range(1, len(result)):
current = result[index]
position = index - 1
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
position -= 1
result[position + 1] = current
return result
print(insertion_sort([9, 5, 1, 4, 3]))Expected output
[1, 3, 4, 5, 9]How it works
Larger prefix values shift right until the current value reaches its correct position. Worst-case time complexity is O(n²).
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.