# Insertion sort

Insertion sort is the King of simple sorting algorithms. It's stable, easy to implement, and acts intelligently while running on presorted arrays and on small arrays (less than a hundred elements). Due to its simplicity, it's even faster than QuickSort on these small arrays.

Insertion sort sees the array as two independent parts - sorted and unsorted.
It continuously selects items from the unsorted part and **inserts them
between items in the sorted part** so that it stays sorted. This is where
its name comes from - it inserts the item exactly where it belongs and avoids
doing any unnecessary actions like Bubble sort
does.

^{2}) which makes it inefficient when compared to smarter algorithms, in these cases.

## Algorithm properties

Time complexity | O(n^{2}) |
---|---|

Stability | Yes |

Speed | High on small arrays |

*Note. the time complexity is according to average cases and the speed is
like this when compared to all of the other algorithms.*

## Process

Consider an array of the following items:

3 | 2 | 5 | 1 | 9 | 4 |

The first item (3) is seen as sorted and the rest of array as unsorted. Let's start up from the second item (2), which we'll save to the auxiliary memory.

Memory: 2

3 | 2 |
5 |
1 |
9 |
4 |

Next, we'll create a space for this item in the sorted part where we'll insert it afterward. We'll move the items in the sorted part to the right until we find an item which is smaller (or equal) to it or to the very beginning of array respectively. It could get a bit confusing that an item is physically written twice in the array since it'll represent an empty space once (highlighted in gray). Theoretically, there isn't anything there, but it'd be inefficient to actually remove the value from the memory.

Let's get back on track, we have 2 saved in the memory which is smaller than 3. Therefore, we'll move the third item to the right. In doing so, we'll lose the item 2, however, we have it saved in the memory, so it doesn't matter.

Memory: 2

3 | 3 | 5 |
1 |
9 |
4 |

There's the beginning of the array before the space we now have created. With that in mind, we'll place the item from the auxiliary memory to the "empty" space. The sorted part of the array now has two items.

Memory: 2

2 | 3 | 5 |
1 |
9 |
4 |

Let's go ahead and sort another item (5).

2 | 3 | 5 |
1 |
9 |
4 |

There is a smaller number before it, so it's already in the right place. The size of the sorted part has increased once more. Let's move on to the next one (1).

2 | 3 | 5 | 1 |
9 |
4 |

Memory: 1

2 | 3 | 5 | 5 | 9 |
4 |

Memory: 1

2 | 3 | 3 | 5 | 9 |
4 |

Memory: 1

2 | 2 | 3 | 5 | 9 |
4 |

Memory: 1

1 | 2 | 3 | 5 | 9 |
4 |

We're pretty much settled in regards to the beginning of the array since no other item is smaller than 1. With that in mind, the (9) will remain in place.

1 | 2 | 3 | 5 | 9 |
4 |

The last item is a (4), so let's get it sorted as well.

1 | 2 | 3 | 5 | 9 | 4 |

Memory: 4

1 | 2 | 3 | 5 | 9 | 9 |

Memory: 4

1 | 2 | 3 | 5 | 5 | 9 |

We'll stop before the (3) and insert the (4) from the auxiliary memory into the empty space we set up. That's it, we're done!

1 | 2 | 3 | 4 | 5 | 9 |

## Visualization

Author of the visualization widget is Jenkings

## Source code

public static void insertionSort(int[] list) { int item, j; for (int i = 1; i <= (list.length - 1); i++) { // insert item item = list[i]; j = i - 1; while ((j >= 0) && (list[j] > item)) { list[j + 1] = list[j]; j--; } list[j + 1] = item; } }

public static void insertionSort(int[] list) { int item, j; for (int i = 1; i <= (list.Length - 1); i++) { // insert item item = list[i]; j = i - 1; while ((j >= 0) && (list[j] > item)) { list[j + 1] = list[j]; j--; } list[j + 1] = item; } }

// sorts the array, assumes indexing from 0 procedure insertion_sort(var list: array of integer) var i, j, item: integer; begin for i:=1 to (length(list) - 1) do begin // insert item item:=list[i]; j:=i - 1; while ((j >= 0) and (list[j] > item)) do begin list[j + 1]:=list[j]; dec(j); end; list[j + 1]:=item; end; end;

def insertion_sort(list) 1.upto(list.length - 1) do |i| # insert item item = list[i] j = i - 1 while ((j >= 0) && (list[j] > item)) list[j + 1] = list[j] j -= 1; end list[j + 1] = item end end