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.
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)
Challenge see if you can find out one extra fact on this topic that we haven't already told you
Click on this link: Insert Sort method