Placement
- Algorithms course
- Beginner
- Lesson 31/80
- 4 min
Place the element in the gap and sort the whole array.
Insertion sort advantages
Insertion sort is very efficient for small or nearly sorted arrays. Since the best case is O(n), it is fast on nearly sorted data.
It also sorts in-place: no extra memory is needed. This is advantageous in memory-constrained systems.
Complexity comparison
Insertion sort has the same O(n^2) complexity as bubble sort and selection sort, but is faster in practice because it does fewer writes.
On nearly sorted arrays, insertion sort is O(n) while bubble sort and selection sort are still O(n^2).
Practice Insertion step
Write insertion_step(arr, i). Shift the i-th element into the sorted part. Print [2, 3, 4, 6] with print(insertion_step([2, 4, 6, 3], 3)).
Starter code
def insertion_step(arr, i):
# Do one stepSample solution
def insertion_step(arr, i):
# Do one step
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key
return arr
print(insertion_step([2, 4, 6, 3], 3))Expected output
[2, 3, 4, 6]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Placement: match the terms
| Term | Meaning |
|---|---|
Insertion sort |
Nearly sorted |
Best |
O(n) |
In-place |
No extra memory |
Few writes |
Fast in practice |
2 On which arrays is insertion sort fastest?
- Reverse sorted
- Random
- Nearly sorted Correct answer
- Very large
Explanation: Fastest on nearly sorted arrays.
3 In-place sorting
Insertion sort requires ____ extra memory.Insertion sort requires little extra memory.Explanation: little is right.