# Insertion sort

Imagine you have a bookshelf with books and you are going to arrange these books in alphabetical order. If amount of books is not big then insertion sort is one of the possible way to sort them.

###### Algorithm

The algorithm relatively divides input array into two parts. First part initially contains only one element and this element is first element of the array. Second part contains rest of elements. Farther, one-by-one each element from second part will be inserted into the first part and into the right place. So that the first part will always be sorted. The array will be sorted when second part of the array becomes empty.

###### Step-by-step example

Let say we have the below books and we want to arrange these books by title:

First of all as per the algorithm description above we need to divide these books into two parts using black vertical line as delimiter (partition):

Now we have two separated parts, first part is already sorted as it contains only one element (“Biology for dummies”) and unsorted part with four other books. Farther, we will iterate over the second part.

First iteration

Step #1: Select first element from the second part (which is “Electronics for dummies”) and compare it with “Biology for dummies”. No changes needed since this pair of books is already sorted.  Just move the delimiter forward. Result:

As you can see our first part now contains two elements (“Biology for dummies” and “Electronics for dummies”) and these elements are sorted.

Second iteration

Step #1: Select “Chemistry for dummies” and compare it with “Electronics for dummies”. Since “Chemistry” should be placed before “Electronics” swap these books and move delimiter forward:

Step #2: Select “Chemistry for dummies” and compare it with “Biology for dummies”. No changes needed since this pair of books is already sorted.

Note: In fact, on each iteration we pick up first element from second part and move it to the left until we reach a smaller element.

Third iteration

Step #1: Select “Dating for dummies” and compare it with “Electronics for dummies”. Since “Dating for dummies” should be placed before “Electronics” swap these books and move delimiter forward:

Step #2: Select “Dating for dummies” and compare it with “Chemistry for dummies”. No changes needed since this pair of books is already sorted.

Fourth iteration

Step #1: Select “Algebra I for dummies” and compare it with “Electronics for dummies”. Since “Algebra I for dummies” should be placed before “Electronics” swap these books and move delimiter forward:

Step #2: Select “Algebra I for dummies” and compare it with “Dating for dummies”. Since “Algebra I for dummies” should be placed before “Dating for dummies” swap these books.

Step #3: Select “Algebra I for dummies” and compare it with “Chemistry for dummies”. Since “Algebra I for dummies” should be placed before “Chemistry for dummies” swap these books.

Step #4: Select “Algebra I for dummies” and compare it with “Biology for dummies”. Since “Algebra I for dummies” should be placed before “Biology for dummies” swap these books.

Now there are no book to compare “Algebra I for dummies” and right part of the array is empty. So this means that all books are sorted and we are done.

###### Implementation

My implementation can be found on GitHub: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/algorithms/sort/InsertionSort.java

We can improve the algorithm using binary search when we inserting element from unsorted part of the array into sorted part. But, to be honest this improvement is not necessary as the insertion sort can be applied only on small arrays and this improvement will not be significant.

###### Complexity

Worst case: O(n^2). Reverse ordered array.

Average case: O(n^2).

Best case: O(n). Array is already sorted.

###### Conclusion
Insertion sort is stable and adaptive sorting algorithm which doesn’t use extra memory. Moreover, this algorithm can sort array as it receives it. But its main disadvantage is quadratic complexity, so it can’t be used to sort big volumes of data. For small arrays it is quite effective and it is better than bubble sort. Because, in practice, insertion sort has less inner iterations (steps in my example) than bubble sort. By this reason insertion sort is used in practice, for instance in quick sort when array is small.
###### Quiz

Q: Which general method use the insertion sort?

A: Insertion method.

Q: Does insertion sort require extra memory?

A: No. This is in-place sort.

Q: Is insertion sort adaptive sorting algorithm?

A: Yes, since best case complexity of insertion sort is O(n).

Q: What is the average and worst case of insertion sort?