# Insertion Sort

## How it works

Insertion sort is a simple sorting algorithm that considers one element at a time in an array of data, and moves that item into its correct place, shifting all other elements along as it does so.

Consider the list above. It is an array of **eight** items, and we wish to sort it into ascending order.

Starting with the **second** item, we ask the simple question: **is this value less than the previous value? **If the answer is **no**, then no action is taken.

However, if the answer is **yes**, then we iterate (loop) through all of the values before that item, until we find the correct location for it. At this point, we shift the remaining items **to the right** one place, freeing up a gap into which to insert the value being moved.

The process then continues, until the end of the list is reached.

Look at the **third** row in the image.

Here, we are looking at element **two** (third item, in green). It less than 9 (the previous element) so it must move. We look at the two values that occur before it and see where it should be inserted. In this case, it is less than 7, the first value. So, the 7 and 9 are both moved to the right one space, freeing up element 0, into which the 6 is placed.

## Pseudocode

sub InsertionSort(data) for i = 1 to len(data) if data[i]<data[i-1] then newPosition = 0 //Find where to insert the value by checking //all values up to current position for j=0 to i if data[j]>data[i] then newPosition = j break end if end for //Store value that's moving in temp variable //Move all items from newPosition to i-1 along one place temp = data[i] for j = i to newPosition data[j+1] = data[j] end for data[newPosition] = temp end if end for end sub

## Advantages

This is a relatively simple algorithm to implement, and because it is **not** recursive, it is easy to step through in the event that something does not work well.

## Disadvantages

The time complexity of this algorithm is O(n^{2}) at its worst, the same as a bubble sort. So, as with the bubble sort, doubling the amount of data will result in the execution time quadrupling. Sorting 100x more data will take 10,000x longer.