8.8. Insertion Sort Code

Once again, taking the algorithm from something appropriate for a human to computer pseudocode requires adding more detail. In the code below, i is equivalent to the black line - it marks the start of the unsorted portion of the list. j is the right hand - it stores the location of the card that is being inserted into place. The animation of a human used the left hand to point to the card to the left of the one being inserted - here we use j - 1 to indicate the card to the left of the card being inserted. (Since j is the index of a location, j - 1 gives us the index to its left.)

    Note: assume that list already exists
1   i = 1                                   i marks start of unsorted cards
2   repeat until (i >= length of the list):
3       j = i                              j is location of current card
4
5       Note: swap the current card left until it finds a home
6       repeat until (j == 0) or (list[j] > list[j - 1])
7           Note: Swap card to the left"
8           temp = list[j]
9           list[j] = list[j - 1]
10          currentMin = list[j]
11          j = j - 1                      current card has moved
12
13      Move the marker showing start of the unsorted portion
14      i = i + 1

Like before, do not worry about memorizing the algorithm, instead use it and the animation below until you can consistently predict the next step before it runs and understand how i and j are getting used.

Animation based on work by Y. Daniel Liang

Why would we care about knowing more than one sorting algorithm? Each approach has its own advantages and disadvantages. Try clicking the “Reset - Partially Sorted” button and then run the sort on a list that is almost in order. Compare how insertion sort works on that list with how the selection sort does on the same list. Which one is more effective?

You have attempted of activities on this page