An insertion sort is less complex and efficient than a merge sort, but more efficient than a bubble sort.
An insertion sort compares values in turn, starting with the second value in the list. If this value is greater than the value to the left of it, no changes are made. Otherwise this value is repeatedly moved left until it meets a value that is less than it. The sort process then starts again with the next value. This continues until the end of the list is reached.
Consider this unsorted list:
12 is the first value in the list. No other values are before it, so the sort moves on to the next value, 14. 14 is greater than the value to the left, 12, so the sort moves on again to the next value, 13. 13 is less than 14, so the two elements are swapped:
13 is greater than 12, so the sort moves onto the next value, 14. 14 is greater than 13, so again the sort moves on.
11 is less than 14, so the two values swap:
11 is less than 13, so the two values swap:
The process repeats:
The list is now sorted into order.
Although more efficient than a bubble sort, insertion sorts work best when used with smaller data sets. Large data sets are more efficiently handled by merge sorts.