Insertion sort

sorting algorithm that, at each iteration, inserts the current input element into the suitable position between the already sorted elements

In computer science, insertion sort is a method of sorting data, such as numbers, one item at a time. It is not a very efficient method compared to other algorithms such as quicksort. However, it is a very simple algorithm that is easy to build.

Graphical example

Think about the sequence of numbers in the picture below. It starts with a small number (written as ≤x), then a big number (≥x) and then a medium sized number (written as x). If this had specific numbers, it might start with 2 (small), 10 (big), 4 (medium). The number 10 is bigger than the number 4. So if the sequence were in order from smallest to biggest, it should start with 2, 4, 10. So the second and third numbers should be swapped. So, in the example below, the sequence should start with ≤x, x, ≥x.


When the sequence it sorted, the medium number is moved in between the small (≤x) and big (≥x) numbers. So the sequence becomes: