Insertion sort

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Graphical example

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.

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.

Insertionsort-before.png


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

Insertionsort-after.png