Insertion sort

Insertion sort works the way many people arrange playing cards in their hand: pick up each new card and slide it into its right place among the cards already held.

• The first element on its own forms the sorted part.
• Each next element is taken out (saved in temp) and inserted into the sorted part at its correct position.
• To find that position, the sorted part is traversed backwards, from right to left. Every element bigger than temp is shifted one place right, making room.
• When a smaller (or equal) element, or the start of the list, is reached, temp is dropped into the gap.

In Algorithm 5.3: temp = numList[i]; then while j >= 0 and numList[j] > temp, shift numList[j] to the right and move j left; finally numList[j+1] = temp.

Example: inserting 1 into the sorted part [7, 8, 13]: 13 is bigger, so it shifts right; so do 8 and 7; the start is reached, and 1 goes in first, giving [1, 7, 8, 13].

If the list is already in order, each new element needs just one comparison, so insertion sort is very fast on nearly sorted data. It is also handy when new items arrive one at a time and must be kept in order.