Insertion sort grows an ordered part one item at a time, placing each new item where it belongs. It is the method a person uses to sort playing cards.
About 3 min of reading
Sort with insertion sort.
Sort a hand of three.
Before you run it, say out loud what it will print. Then open the answer.
Run the in-place version.
Before you run it, say out loud what it will print. Then open the answer.
Save the key before shifting.
Before you run it, say out loud what it will print. Then open the answer.
Sort cards by hand.
Before you run it, say out loud what it will print. Then open the answer.
Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
Insertion sort moves each item only as far as it is out of place. Data that is already close to order sorts almost for free.
Many built-in sorts switch to insertion sort for small chunks. The method is not a dead end, it is a building block.
hand = [5, 3, 4]
out = []
for card in hand:
i = 0
while i < len(out) and out[i] < card:
i += 1
out.insert(i, card)
print(out)Each card is placed in the ordered row at the first spot that fits. The ordered row grows one card at a time.
nums = [1, 2, 3, 9, 4]
print(nums)When items are almost in place, each new one moves only a short way. Insertion sort is quick on nearly sorted data.
nums = [5, 3, 4, 1]
for i in range(1, len(nums)):
key = nums[i]
j = i - 1
while j >= 0 and nums[j] > key:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = key
print(nums)Shift bigger items right, then drop the key in the gap. That is insertion sort without a second row.
nums = [3, 1]
key = nums[1]
print(key)The item being placed is saved first, so shifting does not overwrite it.
rows = [[2, "a"], [2, "b"]]
print(rows[1] < rows[0])An equal item is placed after its equal, not before. Insertion sort keeps equal items in order.
nums = [4, 3, 2, 1]
print(nums)A reversed row moves every item to the front, the most work. That is the n squared worst case.
print(sorted([3, 1, 2]))For a handful of items the cost is tiny. Insertion sort is a good choice for short rows.
cards = [7, 3, 5]
out = []
for c in cards:
out.insert(sum(1 for x in out if x < c), c)
print(out)Sorting by hand is insertion sort: pick a card, slide it into place.
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.