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.

ruthsbookshelf

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:

BECDAA

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):

Bdelimeter_4x115ECDAA

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:

BEdelimeter_4x115CDAA

 

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:

BCEdelimeter_4x115DAA

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:

BCDEdelimeter_4x115AA

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:

BCDAAEdelimeter_4x115

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.

BCAADEdelimeter_4x115

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.

BAACDEdelimeter_4x115

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.

AABCDEdelimeter_4x115

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

bubble_sort_plot

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?
Click here to check your answer.

A: Insertion method.

Q: Does insertion sort require extra memory?
Click here to check your answer.

A: No. This is in-place sort.

Q: Is insertion sort adaptive sorting algorithm?
Click here to check your answer.

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

Q: What is the average and worst case of insertion sort?
Click here to check your answer.

A: O(n^2).

Q: Does insertion sort use comparison?
Click here to check your answer.

A: Yes.

Q: Is insertion sort stable sorting algorithm?
Click here to check your answer.

A: Yes, it doesn’t  change relative order of already sorted elements.

Leave a Reply