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

Conclusion

Quiz