Insert Sort
lConsider what is sometimes called “an ordered list,” and treated as a different component from a list.
lWe see that such a
distinction is not necessary at all, since
one can produce an ordered list without ever using a pointer or reference. We can simply use the list_position as defined, and as new items are inserted, we advance along the list until we find the position we want to satisfy the ordering requirement and then call Insert.