7. Insertion sort

This is a simple comparison sort where the sorted list is built up one item at a time.

Algorithm

1. Take any item from the unsorted part of the list
2. Compare it to each item in the already-sorted part of the list
3. If the item is found to be in-between the values of two existing sorted items, then insert it between the two items.
4. Repeat the process until all the items have been sorted.

To clarify, consider a partially sorted list

2 5 5 8 9      3

The numbers on the left have already been sorted, now the unsorted 3 needs to be inserted into the final list.
Start by comparing 3 to the rightmost sorted item (9). If it is less, then try the next item (8). Repeat until a value less than the item is found (2). Now insert the 3 to the right of the item

2 3 5 5 8 9 

Instead of a linear search, a binary search could also have been used to find the correct location in the list because the comparison is being made over an ordered list. This will speed up the process

Advantages of insert sort

• Simple to code
• Very good performance with small lists (how small is small depends on the power of the computer it is running on)
• Very good when the list is almost sorted. In this case very few compares need to be done. The worst case is when the list is in reverse order.
• Sort-stable which means it keeps the relative positions of the elements intact
• Very memory efficient - it only needs one extra storage location to make room for the moving items.
• Good with sequential data that is being read in one at a time e.g. tape, hard disk or data being received sequentially.
  

Disadvantage of insertion sort compared to alternatives

• Poor performance with large lists.
• Not as quick as merge sort or quicksort