# Algorithm of the Week: Insertion Sort

Sorted data can dramatically change the speed of our program. Therefore, sorting algorithms are something quite special in computer
science. For instance searching in a sorted list is faster than
searching in an unordered list.

There are two main approaches in sorting – by comparing the elements
and without comparing them. A typical algorithm from the first group is
insertion sort. This algorithm is very simple and very intuitive to
implement, but unfortunately it is not so effective compared to other
sorting algorithms such as quicksort and merge sort. Indeed, insertion sort is useful for small sets of data with about no more than 20 items.

Insertion sort is a very intuitive method of sorting items and we
often use it when we play card games. In this case the player often gets
an unordered set of playing cards and intuitively starts to sort it.
First by taking a card, making some comparisons and then putting the
card in the right position.

So let’s say we have an array of data. In the first step the array is unordered, but we can say that it consists of two sub-sets: sorted and unordered, where on the first step the only item in the sorted sub-set is its first item. If the length of the array is n the algorithm is considered completed in n-1 steps. On each step our sorted subset is growing with one item. The thing is, we take the first item from the unordered sub-set and with some comparisons we put it into its place in the sorted sub-set, like on the diagram bellow.

### Main principle of insertion sort.

The insertion itself is the tricky part. We can insert the item once we find an item with a smaller value or if we have reached the front of the array like on the diagram bellow.

### Example of insertion sort

## Implementation

Here’s a quick implementation of insertion sort in PHP. The good thing is that it is easy to implement, but there's bad news too – insertion sort is slow and ineffective for large data sets.

$data = array(4, 2, 4, 1, 2, 6, 8, 19, 3); function insertion_sort(&$arr) { $len = count($arr); for ($i = 1; $i < $len; $i++) { $tmp = $arr[$i]; $j = $i; while (($j >= 0) && ($arr[$j-1] > $tmp)) { $arr[$j] = $arr[$j-1]; $j--; } $arr[$j] = $tmp; } }

We can improve this code a little by using a sentinel, just like the
sequential search, in order to remove one of the comparisons.

$data = array(4, 2, 4, 1, 2, 6, 8, 19, 3); function insertion_sort_sentinel(&$arr) { $len = count($arr); array_unshift(&$arr, -1); for ($i = 1; $i < $len+1; $i++) { $tmp = $arr[$i]; $j = $i; while ($arr[$j-1] > $tmp) { $arr[$j] = $arr[$j-1]; $j--; } $arr[$j] = $tmp; } array_shift(&$arr); // remove the sentinel }

Since we used searching in the right position in an ordered array,
we can use binary search in order to improve the above algorithm even more. Unfortunately this doesn’t do much to improve the general efficiency
of this algorithm.

## Complexity

As I said this algorithm is not very effective. Its complexity is O(n^{2}) which is far worse than the O(n*log(n)) of quicksort, as you can see on the diagram bellow.

### n*n vs. n*log(n)

- It is easy to implement
- It does not require additional memory
- It can be fast if the data is almost nearly sorted

Which is great!*Source: http://www.stoimen.com/blog/2012/02/13/computer-algorithms-insertion-sort/*

{{ nComments() }}