## Method

**Insertion sort** is an algorithm to arrange a sequence of elements
*R*_{1}, *R*_{2}, …, *R*_{n}
into order. Elements are removed one by one from the unsorted sequence and
inserted into the correct position in a new, sorted sequence *S*.

Sorting is usually implemented in-place. As elements are removed from the
end of sequence *R*, the space freed up is used to extend sequence
*S*. After *i* insertions, *R*_{1}, …,
*R*_{n-i} remain unsorted and the sorted sequence
*S*_{1}, …, *S*_{i} is stored in elements
*R*_{n-i+1}, …, *R*_{n}.

## Pseudo-code

`function insertion_sort `*R*
*i* ← length *R*
while *i* > 0 do
*j* ← *i*
*temp* ← *R*_{j}
while *j* < length *R* and *R*_{j+1} < *temp* do
*R*_{j} ← *R*_{j+1}
*j* ← *j* + 1
*R*_{j} ← *temp*
*i* ← *i* - 1

## Example

The example below shows the steps necessary to sort 6 elements. White elements are unsorted, grey elements have been sorted and the red element has been inserted in the current step.

833 | 197 | 153 | 634 | 889 | 381 |

833 | 197 | 153 | 634 | 889 | 381 |

833 | 197 | 153 | 634 | 381 | 889 |

833 | 197 | 153 | 381 | 634 | 889 |

833 | 197 | 153 | 381 | 634 | 889 |

833 | 153 | 197 | 381 | 634 | 889 |

153 | 197 | 381 | 634 | 833 | 889 |

## Analysis

Insertion sort requires *n* passes to sort a sequence of *n*
elements. With each pass the sorted sequence *S* increases by one
element. On average, Insertion sort will move and compare half of the sorted
sequence each pass. The average number of move / compare operations is
(*n*²-*n*)/4.

The worst case is a sequence sorted in reverse order which requires
(*n*²-*n*)/2 move / compare operations. Insertion sort runs
in Ο(*n*²) time.

Insertion sort is a stable sorting algorithm. The relative order of equal elements is maintained.

## Implementation in Redcode

```
org outer
temp equ (outer-1)
outer nop }z, {q
z mov #0, y
q mov.a #FIRST+LENGTH-p,p
p mov #0, #0
mov {p, temp
inner slt @p, temp
jmp found
mov >p, }p
y djn inner, #0
found mov temp, *p
djn outer, #LENGTH-1
```

## Comparison to other Ο(*n*²) sort algorithms

Insertion sort is 11 instructions long in Redcode, the same size as Bubble sort. Gnome sort and Selection sort are both shorter, at 9 and 10 respectively.

For the worst case the Redcode Insertion sort requires
1.5*n*²+5.5*n*-7 cycles to sort *n* elements, the
same length of time as Selection sort. Bubble sort and Gnome sort are
both slower, taking 3*n*²-3 and 4.5*n*²-3.5*n*
respectively. The table below shows the number of cycles required to
sort *n* elements:

n | Insertion | Selection | Bubble | Gnome |
---|---|---|---|---|

2 | 10 | 10 | 9 | 11 |

3 | 23 | 23 | 24 | 30 |

4 | 39 | 39 | 45 | 58 |

5 | 58 | 58 | 72 | 95 |

10 | 198 | 198 | 297 | 415 |

15 | 413 | 413 | 672 | 960 |

20 | 703 | 703 | 1197 | 1730 |

50 | 4018 | 4018 | 7497 | 11075 |

75 | 8843 | 8843 | 16872 | 25050 |

100 | 15543 | 15543 | 29997 | 44650 |

150 | 34568 | 34568 | 67497 | 100725 |

200 | 61093 | 61093 | 119997 | 179300 |