🧮Insertion Sort
Also known as Insertion Sorting, Card Sort
Take each item in turn. Slide it back to its right place.
Think of it like
It is like sorting cards in your hand. You pick up one card at a time and slide it into place.
Example
A list of 20 scores is in order except for one new score at the end. Insertion sort fixes it in a few steps.
Why it matters
It is simple and quick on small or nearly sorted lists. Real sorting code uses it for that job.
Definition
Example code
python
def insertion_sort(a):
for i in range(1, len(a)):
x, j = a[i], i - 1
while j >= 0 and a[j] > x:
a[j + 1] = a[j]
j -= 1
a[j + 1] = x
return aCommon mistake
Key takeaways
- 1Grows a sorted part. One item joins it each step.
- 2Great when nearly sorted. Few moves are needed.
- 3Slow on big messes. About n squared steps.