Background

Basic sorts such as bubble sort and insertion sort typically run in O(N²) time where N is the number of elements. This complexity makes these sorts exponentially slower as the size of the list being sorted increases.

In an insertion sort, we go from left to right, visiting each index in the list to be sorted starting with index 1 (assuming a zero-indexed list). Our goal is to insert each visited element in its proper position within the sub-list composed of all the elements to its left. If the visited element is greater than the element to its left, then due to the insertion sort invariant (described below) it is greater than all the elements to its left and does not need to be moved.

Insertion Sort Algorithm

Let’s call the currently selected index, the marker index, and the element at that index, the marker element.

Identify the insertion position of marker element:  If the marker element is greater than the element to its left, then it is already in its proper position and we can advance to the next index in the list by incrementing the marker index by 1.

If not, the insertion position of the marker element is the position within the (by definition, sorted) sub-list formed by all elements to its left, such that all elements before the insertion position are less than or equal to the marker element, and all elements after the insertion position up to the marker index are greater than the marker element.

Note: If the marker element is smaller than all elements to its left, its insertion position will be the beginning of the list (index 0).

Insert marker element in the insertion position: Our next step is to move the marker element to the identified insertion position. We shift each element in the sub-list that is greater than the marker element (each element between the insertion position and the marker index) one position to the right, starting from the identified insertion position and moving up to the marker index. This creates an empty slot at the insertion position, into which we then place the marker element.

Now that the marker element is in its correct position in the sub list to the left of the marker index, we increment the marker index by 1. We repeat this until the marker index reaches the end of the list.

Invariant: In an insertion sort, the invariant (the condition that is always true during the execution of the sort) is that the sub-list formed by elements to the left of the right-traveling marker index is always fully sorted.

Insertion Sort Efficiency Analysis

For N numbers, the marker moves to the right N-1 times and each time the marker is moved,  there are as many comparisons as the current value of the right-moving marker index (1,2,3…N-1).

Hence the worst-case number of comparisons in one full run of the insertion sort is ∑(N-1) which is N(N-1)/2.

However on average, assuming uniformly random data, for each marker position at index n, we perform about n/2 comparisons since the insertion point is equally likely to be anywhere in the sorted sub-list to the left of the marker position, and hence the total number of comparisons for the average full run of the insertion sort is half of the worst case, or 1/2*∑(N-1) which is N(N-1)/4.

The total number of element shifts (when the element is moved one place to the right to accommodate the space made for the marker element) is approximately the same as the number of comparisons since each comparison that leads to insertion requires shifting one element to the right.

Thus the total number of operations – comparisons plus right shifts – on an average insertion sort is 2 * N(N-1)/4, which is N(N-1)/2.

Insertion Sort vs Bubble Sort complexity

While the insertion sort runs in O(N²) time, it still runs about twice as fast as the bubble sort since the number of comparisons and element copies (to their adjacent position) are on average about half the number of element comparisons and swaps that happen in the bubble sort.

Also, a copy operation (the basic repeated operation in an insertion sort) is less time consuming than a swap operation (the basic repeated operation in a bubble sort).

In a best case scenario, when the array is already sorted, no shifts are required and insertion sort completes in linear time: O(N). In the worst case scenario, if the data is inversely sorted, each marker must be inserted at position 0, and the insertion sort has to do n comparisons and shifts for a marker value of n, rather than the average n/2, and hence the insertion sort degenerates to O(N²) time, which is the efficiency of the bubble sort.