Insertion sort is a method of sorting a list.
It is very simple - it simply takes each item and loops through the (semi) sorted list to put it in the right place.
It uses the first item in the list as a 'starting-point'
Algorithm[edit | edit source]
- Look at the second item in a list.
- Compare it to all the items that are before it and insert the number in the correct place.
- Repeat {2} for all subsequent items in the list.
Advantages[edit | edit source]
- Intuitive way of sorting things
- Easy to implement (code)
- Low memory usage
- Very quick to add items (if list is ordered)
- Works well with small lists
- Quick to check if list is already sorted.
Disadvantages[edit | edit source]
Like the bubble sort, it doesn't work efficiently with larger lists.
Speed of insertion sort[edit | edit source]
In the best case scenario (already ordered list), it takes n-1 comparisons.
In the worst-case scenario, it takes n(n-1) / 2 comparisons.