Insertion Sort algorithm

This article explains how to implement and use the Insertion Sort algorithm. One of the simplest, but at the same time powerful ones. The Code examples would be in Java, but can be easily converted to any other programming language. If you want to have a summary, just scroll to a summary section.

During the topic, we would be sorting the following array [1, 5, 3, 1, 4]. All examples would be related to this array.

Insertion Sort

The algorithm itself is pretty simple. Here is a pseudo-code of implementation.

function InsertionSort(input)
    for i = 1 to length(input) - 1 do //2
        element = input[i]
        j = i - 1
        while j > 0 and input[j] > element do
            input[j + 1] = input[j]
            j = j - 1
        input[j + 1] = element

    return input

The main idea is to have a sorted subarray on the left side and then insert the next element from the right unsorted rest of the array into the appropriate place in the sorted part.

Sorting starts with the 1^st indexed element, not with 0^th indexed since a single-element array is always sorted. Each next element from the unsorted part is moved to the left to find its place, i.e. insert into the correct position. The position is correct when the element with index i-1 is smaller or equals the element the is being moved/inserted.

Starting with 1^th indexed element which is 5.

The element is not smaller than previous one so no need to move it. It is in place. Now 1 and 5 are sorted.

Next element is 3 with index 2.

It is smaller than the previous one with the index 1, it is necessary to shift 5 to the right by one cell. Now compare 3 with the element with index 0. It is not smaller than 1, so placing 3 to the cell with index 1. The same approach will be applied and further. Taking the following element 1 with the index 3.

This time 1 is smaller than two elements, two must be shifted. Since the comparison operation is strictly smaller, the algorithm will not move 1 from cell 0 which is not necessary. The last element is 4

Only one element is needed to be shifted to the right to pace 4 in the necessary position. That is it, the array has been sorted.

A Java implementation is pretty straight forward.

    int[] insertionSort(int[] input) {
        for (var i = 1; i < input.length; i++) {
            var element = input[i];
            var j = i - 1;
            for (; j > 0 && input[j] > element; j--) {
                input[j + 1] = input[j];
            }
            input[j + 1] = element;
        }
        return input;
    }

A main loop that starts with index 1 and a sub-loop that traverses backward to shift as many elements as necessary to the right to place the current one.

The animation of the whole process from Wiki.

Complexity and Characteristics

From the Space Complexity standpoint algorithm uses constant space as there are always three variables, two for indexes and one element before it can be inserted: O(1).

The time complexity is much worse due to a nested loop, resulting in a quadratic time of O(N*N). Indeed, in the worse case when the array is sorted descendent to sort it ascendant each element must be shifted to the mirrored position, i.e. the first would become the last and the last will become the first one. Which requires ~ N moves for each element, as a result ~ N * N moves.

The algorithm is stable as keeps relative order during sorting, i.e. if there are two same elements A and B their order after the sort will be the same.

It is also in-place as the original array is being used for sorting and doesn't require creating a new one.

Last but not least, the algorithm is online and allows adding new elements later on without a need to perform full resorting.

Applicability

The algorithm is not the fastest one, but it is still could be used in certain scenarios efficiently.

One of such cases is when an array is semi-sorted (only few elements aren't in place) or each entry located close to the final position. Sorting would require a small number of moves for each entry and in total ~ N moves.

The best scenario for usage is when there is a huge sorted part and a relatively small unsorted part is added. In such a case sorting would take approximately N * K moves where K is number of the new elements added. In other words, for each new number, there are around ~ N moves. This advantage comes from the online characteristic and is much better than sorting from scratch taking O(N * log N) time for the most of algorithms.

Summary

The Insertion Sort algorithm is not a very productive one with O(N * N) time complexity and O(1) space complexity. But works very well for semi-sorted arrays. An online characteristic makes it suitable and efficient for adding new elements to an already sorted one. It is also stable and in-place.

Links

https://en.wikipedia.org/wiki/Insertion_sort
https://www.bigocheatsheet.com/
https://en.wikipedia.org/wiki/Category:Stable_sorts
https://en.wikipedia.org/wiki/In-place_algorithm
https://www.amazon.com/Algorithms-Java-Parts-1-4-Pts-1-4/dp/0201361205
https://www.amazon.com/Introduction-Algorithms-fourth-Thomas-Cormen/dp/026204630X/ref=sr_1_1