Insertion Sort algorithm

#algorithms #sort #insertion #java

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 the 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, the unsorted rest of the array, into the appropriate place in the sorted part.

Sorting starts with the 1^st indexed element, not with the 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., inserted into the correct position. The position is correct when the element with index i-1 is smaller than or equal to the element that is being moved/inserted.

Starting with the 1^st indexed element, which is 5.

The element is not smaller than the 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 in the cell with index 1. The same approach will be applied further. Taking the following element 1 with the index 3.

This time, 1 is smaller than two elements, so 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 needs to be shifted to the right to place 4 in the necessary position. That is it, the array has been sorted.

A Java implementation is pretty straightforward.

    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 the 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 worst case, when the array is sorted descending to sort it ascending, each element must be shifted to the mirrored position, i.e., the first would become the last, and the last would become the first. Which requires ~ N moves for each element, as a result - ~ N * N moves.

The algorithm is stable as it 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 the need to perform a full re-sorting.

Applicability

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

One of such cases is when an array is semi-sorted (only a few elements aren't in place) or each entry is 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 the number of new elements added. In other words, for each new number, there are around ~ N moves. This advantage stems from the online characteristic and is much better than sorting from scratch, taking O(N * log N) time for most 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.