Insertion Sort

Insertion sort builds a sorted list one item at a time. The left part of the list is treated as sorted and the right part as unsorted; to begin with, the sorted part is just the first item, because a list of one item is always in order.

Inserting the next item

Pick out the next item from the unsorted section; this is the current item. Look back through the sorted section, starting at its right-hand end. Any item that is bigger than the current item moves one place to the right, opening up a gap. When you reach an item that is smaller than the current item, or you run out of items to check, put the current item into the gap. Keep going until the unsorted section is empty.

The inner loop that does the shifting is condition-controlled: it repeats while there is still an item to the left and that item is larger, because you cannot know in advance how many shifts a particular item will need.

Worked example: putting books in page-count order

Suppose five books have page counts 320, 180, 250, 140 and 210. We want them on the shelf from fewest pages to most pages.

The same steps written in Python, working on the five page counts from the table: each item is held in a variable while the larger items shuffle right, then dropped into the gap.

pages = [320, 180, 250, 140, 210]
for next_index in range(1, len(pages)):
    held = pages[next_index]
    gap = next_index - 1
    while gap >= 0 and pages[gap] > held:
        pages[gap + 1] = pages[gap]   # shift the larger page count right
        gap = gap - 1
    pages[gap + 1] = held             # put the held page count into the gap
print(pages)

Output:

[140, 180, 210, 250, 320]

For descending order you use exactly the same algorithm and reverse the comparison, shifting items that are smaller than the current item.