Editing Insertion sort

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 ==

# 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 ==

* 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 ==
Like the bubble sort, it doesn't work efficiently with larger lists.

== Speed of insertion sort ==
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.