Insert Sort

Used to quickly arrange information into a certain order.

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 list
2. Compare it to each item in the already-sorted 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

Advantages of insert sort

• Simple to code
• Very good performance with small lists (how small is small depends on the power of the computer the sort 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 quick sort (see the glossary for these as well)

2020-10